如何设计具有可变数据大小的FIFO队列？ [英] How do you design FIFO queue with variable data size?

问题描述

我正在处理FIFO队列（简单的一点，就是首先推出的，首先弹出），但是我不知道如何设计它。我将在那里存储的数据类型将提前知道，让我们说这个类的每个实例都是一样的。我正在考虑使用TList，其中具有以下定义的记录将被存储（@David - 它是D2007，所以我没有 Generics.Collections 可用：）

 键入
 PListItem = ^ TListItem ; 
 TListItem = record 
大小：整数; //以下成员指向的数据大小
数据：指针; //指向内存中保留的目标数据
 end; 
  

与这样的实现（我在这里假装一切正常，所以没有异常处理使用）

 键入
 TListQueue = class 
 private 
 FList：TList; 
 public 
构造函数创建; 
析构函数覆盖
程序清除; 
 procedure push（const value; const Size：Integer）; 
 procedure Pop（var Value; var Size：Integer）; 
结束
 
构造函数TListQueue.Create; 
开始
继承; 
 FList：= TList.Create; 
结束
 
析构函数TListQueue.Destroy; 
开始
清除; 
 FList.Free; 
继承; 
结束
 
程序TListQueue.Push（const value; const Size：Integer）; 
 var ListItem：PListItem; 
 begin 
 New（ListItem）; 
 ListItem.Size：= Size; 
 ListItem.Data：= AllocMem（Size）; 
 Move（Value，ListItem.Data ^，Size）; 
 FList.Add（ListItem）; 
结束
 
程序TListQueue.Pop（var Value; var Size：Integer）; 
 var ListItem：PListItem; 
 begin 
如果FList.Count> 0然后
 begin 
 ListItem：= FList.Items [0]; 
大小：= ListItem ^ .Size; 
 Move（ListItem.Data ^，Value，ListItem.Size）; 
 FreeMem（ListItem.Data，ListItem.Size）; 
 Dispose（ListItem）; 
 FList.Delete（0）; 
结束
结束
 
程序TListQueue.Clear; 
 var I：整数; 
 ListItem：PListItem; 
 begin 
 for I：= 0 to FList.Count  -  1 do 
 begin 
 ListItem：= FList.Items [I]; 
 FreeMem（ListItem.Data，ListItem.Size）; 
 Dispose（ListItem）; 
结束
 FList.Clear; 
结束
  

我的问题是：


这是有效的方式如何对于大小从几个字节到大约1MB的FIFO（队列（诸如字符串，流，记录）的数据类型）进行FIFO队列（如果是流）？

非常感谢>

解决方案

为什么不使用：

 键入
 PListItem = ^ TListItem; 
 TListItem = record 
大小：整数; //以下成员指向的数据大小
数据：指针; //指向内存中保留的目标数据
下一页：PListItem; //指向下一个数据项的指针，或最后一个的nil。 
结束
  

您还需要一个 var Root：PListItem = nil; 并用New（）和Dispose（）分配/取消分配项。您可能需要添加一个 var LastItem：PListItem = nil; ，其中包含列表中的最后一个项目，因此您不必每次都会遍历整个列表要添加一个项目。

与现代基于对象的解决方案相比，仍然是原始的，对于FIFO解决方案，单个链表仍然非常有效。不太优雅，但嘿，它的效果很好。如果你想要更多的优雅，围绕这个建立一个课程！

I'm just working on the FIFO queue (the simple one, just what's pushed first, pops at first) with the variable data size but I'm not sure with the way I'm designing it. The data types I will store there will be known in advance and let's say will be the same for each instance of this class. I was thinking about using TList where the records with the following definition will be stored (@David - it's for D2007, so I have no Generics.Collections available :)

type
  PListItem = ^TListItem;
  TListItem = record
    Size: Integer; // size of the data pointed by the following member
    Data: Pointer; // pointer to the target data reserved in memory
  end;

with the implementation like this (I'm pretending here that everything works fine, so no exception handling is used)

type
  TListQueue = class
private
  FList: TList;
public
  constructor Create;
  destructor Destroy; override;
  procedure Clear;
  procedure Push(const Value; const Size: Integer);
  procedure Pop(var Value; var Size: Integer);
end;

constructor TListQueue.Create;
begin
  inherited;
  FList := TList.Create;
end;

destructor TListQueue.Destroy;
begin
  Clear;
  FList.Free;
  inherited;
end;

procedure TListQueue.Push(const Value; const Size: Integer);
var ListItem: PListItem;
begin
  New(ListItem);
  ListItem.Size := Size;
  ListItem.Data := AllocMem(Size);
  Move(Value, ListItem.Data^, Size);
  FList.Add(ListItem);
end;

procedure TListQueue.Pop(var Value; var Size: Integer);
var ListItem: PListItem;
begin
  if FList.Count > 0 then
  begin
    ListItem := FList.Items[0];
    Size := ListItem^.Size;
    Move(ListItem.Data^, Value, ListItem.Size);
    FreeMem(ListItem.Data, ListItem.Size);
    Dispose(ListItem);
    FList.Delete(0);
  end;
end;

procedure TListQueue.Clear;
var I: Integer;
    ListItem: PListItem;
begin
  for I := 0 to FList.Count - 1 do
  begin
    ListItem := FList.Items[I];
    FreeMem(ListItem.Data, ListItem.Size);
    Dispose(ListItem);
  end;
  FList.Clear;
end;

My question is:

Is this the efficient way how to make FIFO queue (for data types like strings, streams, records) with size from several bytes to about 1MB (in case of stream) ?

Thanks a lot

解决方案

Why not use:

type
  PListItem = ^TListItem;
  TListItem = record
    Size: Integer; // size of the data pointed by the following member
    Data: Pointer; // pointer to the target data reserved in memory
    Next: PListItem; // pointer to the next data entry, or nil for the last one.
  end;

You would also need a var Root: PListItem = nil; and allocate/deallocate items with New() and Dispose(). You might want to add a var LastItem: PListItem = nil; which contains the last item in your list so you don't have to walk through the whole list every time when you want to add an item.
While still primitive compared to modern "object-based solutions", a single linked-list is still very efficient for a FIFO solution. Not too elegant but hey, it works well enough. If you want more elegance, build a class around this all!

这篇关于如何设计具有可变数据大小的FIFO队列？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！