Модераторы: Snowy, MetalFan, bems, Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Быстрая сортировка больших массивов данных, Наиболее быстрый метод сортировки 
:(
    Опции темы
Freimaks
Дата 19.4.2012, 11:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 23.4.2011

Репутация: нет
Всего: нет



Ну вроде прочитал, не могу сказать что понял 100% все, но кое что прояснилось в моей голове.
Завел один класс TBinPoints, в качестве полей класса описал все возможные поля записи в bin-файле, определил их свойства и сделал три конструктора (по одному для каждого из типов файлов).
Далее как понял мне все-равно надо использовать записи, чтобы считывать файл. Завел соответственно 3 записи, которые использую для BaseStream.Read(Запись, SizeOf(запись)).
Вроде все правильно, да и все работает.
Я не могу понять теперь, что мне использовать в качестве Key в TDictionary. Ради интереса я делал так: 
Код

TDictionary<integer, TBinPoints>.Create;

И далее в качестве Key использовал BinPoints.PointCode (типа класс) и в итоге у меня в TDictionary оставалось количество записей=количеству разных классов.
Потом в качестве Key попробовал указывать MD5 от строки из координат... работает конечно - но долго до невозможности.
В общем пока остались вопросы по Key в TDictionary.
PM MAIL   Вверх
Qu1nt
Дата 19.4.2012, 23:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 602
Регистрация: 13.1.2007

Репутация: 22
Всего: 50



Читай про устройство хеш-таблиц. Вот, один из простеньких вариантов:
Код

type
  TPoint = class
    X: Integer;
    Y: Integer;
    Z: Integer;
    constructor Create(const X, Y, Z: Integer);
  end;

  TPointComparer = class(TEqualityComparer<TPoint>)
    function Equals(const Left, Right: TPoint): Boolean; override;
    function GetHashCode(const Value: TPoint): Integer; override;
  end;

  TPointSolver = class
    Points: TList<TPoint>;
    constructor Create(const Points: TList<TPoint>);
    procedure DeleteDuplicates(const Comparer: IEqualityComparer<TPoint>);
    procedure PrintPoints(const Output: TStrings; const Details: String = '');
  end;

constructor TPoint.Create(const X, Y, Z: Integer);
begin
  Self.X := X;
  Self.Y := Y;
  Self.Z := Z;
end;

function TPointComparer.Equals(const Left, Right: TPoint): Boolean;
begin
  Result := (Left.X = Right.X) and (Left.Y = Right.Y) and (Left.Z = Right.Z);
end;

function TPointComparer.GetHashCode(const Value: TPoint): Integer;
begin
  Result := 17;
  Result := Result * 23 + Value.X;
  Result := Result * 23 + Value.Y;
  Result := Result * 23 + Value.Z;
end;

constructor TPointSolver.Create(const Points: TList<TPoint>);
begin
  Self.Points := Points;
end;

procedure TPointSolver.DeleteDuplicates(const Comparer: IEqualityComparer<TPoint>);
var
  Dictionary: TDictionary<TPoint, Integer>;
  I: Integer;
begin
  Dictionary := TDictionary<TPoint, Integer>.Create(Comparer);
  try
    for I := Points.Count - 1 downto 0 do
      if Dictionary.ContainsKey(Points[I]) then
        Points.Delete(I)
      else
        Dictionary.Add(Points[I], 0);
  finally
    Dictionary.Free;
  end;
end;

procedure TPointSolver.PrintPoints(const Output: TStrings; const Details: String = '');
var
  Point: TPoint;
begin
  Output.Append(Details);
  for Point in Points do
  begin
    Output.Append(Format('X: %d Y: %d Z: %d', [Point.X, Point.Y, Point.Z]));
  end;
end;

procedure TestPointSolver(const Output: TStrings);
var
  Points: TList<TPoint>;
begin
  Points := TObjectList<TPoint>.Create();
  try
    Points.AddRange([TPoint.Create(0, 0, 0), TPoint.Create(0, 0, 1),
      TPoint.Create(0, 1, 0), TPoint.Create(0, 0, 0), TPoint.Create(0, 0, 1)]);
    with TPointSolver.Create(Points) do
    try
      PrintPoints(Output, 'Before delete duplicates:');
      DeleteDuplicates(TPointComparer.Create);
      PrintPoints(Output, 'After delete duplicates:');
    finally
      Free;
    end;
  finally
    Points.Free;
  end;
end;

PM MAIL   Вверх
Freimaks
Дата 20.4.2012, 07:50 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 23.4.2011

Репутация: нет
Всего: нет



Решил проблему с ключом несколько иначе: создал запись из пяти полей (X,Y,Z,Time,Code) и в качестве ключа использую эту запись в соответствии с требованиями подхода - либо только 4 поля, либо все 5. Вроде работает, дубли ищет.
В примере как я понял ключ генерится с помощью function TPointComparer.GetHashCode(const Value: TPoint): Integer;.
Как работают хеш-таблицы я почитал - я хотел примерно такое же сделать ручками на базе двух массивов, но так как потом получилось завести Dictionary, то решил на это забить.
В принципе то, что я сваял на данный момент работает, но не идеально.

PM MAIL   Вверх
Qu1nt
Дата 20.4.2012, 09:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 602
Регистрация: 13.1.2007

Репутация: 22
Всего: 50



К сожалению, стандартного шаблонного множества в Delphi нет, как и аналога С++ std::multimap. Поэтому для экономии памяти я бы использовал в TDictionary только поле ключа. И в зависимости от задачи менял только компаратор.
PM MAIL   Вверх
Freimaks
Дата 20.4.2012, 12:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 23.4.2011

Репутация: нет
Всего: нет



Цитата(Qu1nt @  20.4.2012,  07:30 Найти цитируемый пост)
Поэтому для экономии памяти я бы использовал в TDictionary только поле ключа. И в зависимости от задачи менял только компаратор. 

Да, это актуально, т.к. памяти все это жрет не мало.
Но больше всего меня беспокоит скорость чтения\записи. Я думал, что торможение идет в следствии различных операций переброса значений в класс, в запись в Dictionary.
Но это влияет в меньшей степени.
Сделал отдельную процедуру просто для чтения одного файла.
Код

procedure TForm1.Button2Click(Sender: TObject);
var g:integer;
begin
g:=1;
with TBinaryReader.Create('d:\data\2332371--.bin') do
try
BaseStream.Read(BinHeader, SizeOf(BinHeader));
ProgressBar1.Min:=1;
ProgressBar1.Max:=BinHeader.PntCnt;
while basestream.Position<>basestream.Size do
begin
Application.ProcessMessages;
BaseStream.Read(RPointsTime, SizeOf(RPointsTime));
ProgressBar1.Position:=g;
g:=g+1;
end;
finally
  Free;
end;
end;

Чтение этого файла размеров в 53.3 мегабайта занимает около 30 секунд... если не больше.
Можно как-то ускорить. Хотя бы куда копать не подскажете?
PM MAIL   Вверх
Qu1nt
Дата 20.4.2012, 12:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 602
Регистрация: 13.1.2007

Репутация: 22
Всего: 50



Как ситуация меняется, если убрать взаимодействие с пользовательским интерфейсом? Убери Application.ProcessMessages и ProgressBar из цикла.
PM MAIL   Вверх
Freimaks
Дата 20.4.2012, 13:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 23.4.2011

Репутация: нет
Всего: нет



Сократил до минимума... толку никакого. Я просто понять не могу в чем проблема - т.е. я что-то делаю не так, инструмент медленный или что вообще не так. В родной проге этот файл открывается за 1-2 секунды...
Код

procedure TForm1.Button2Click(Sender: TObject);
begin
with TBinaryReader.Create('d:\OPTEN\TPMAK\data\With_thinpoint_2332371--.bin') do
try
BaseStream.Read(BinHeader, SizeOf(BinHeader));
while basestream.Position<>basestream.Size do
BaseStream.Read(RPointsTime, SizeOf(RPointsTime));
ShowMessage('Готово');
finally
Free;
end;
end;

RPointsTime - это packed record.
PM MAIL   Вверх
Qu1nt
Дата 20.4.2012, 13:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 602
Регистрация: 13.1.2007

Репутация: 22
Всего: 50



Хорошо, в таком случае нужно читать блочно. Попробуй за раз читать несколько тысяч точек. 
PM MAIL   Вверх
Freimaks
Дата 20.4.2012, 13:41 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 23.4.2011

Репутация: нет
Всего: нет



Цитата(Qu1nt @  20.4.2012,  11:39 Найти цитируемый пост)
Хорошо, в таком случае нужно читать блочно. Попробуй за раз читать несколько тысяч точек.  

А не подскажите, как это сделать???
PM MAIL   Вверх
Freimaks
Дата 20.4.2012, 15:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 23.4.2011

Репутация: нет
Всего: нет



Я понял как делать!!! Ща усе сделаю smile
PM MAIL   Вверх
Qu1nt
Дата 20.4.2012, 22:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 602
Регистрация: 13.1.2007

Репутация: 22
Всего: 50



Только добрался до компилятора. Ага, оказывается свойства Position и Size не кэшируются, отсюда такое проседание. Добавив буфер и исправив этот момент получил значительный прирост в производительности. Загрузка 200 МБ файла в список у меня занимает меньше секунды.
Код

procedure ReadWithBuffer(const FileName: String);
const
  MAX_BUFFER_SIZE = 10000;
var
  PointsBuffer: array of TPackedPoint;
  Points: TList<TPoint>;
  TotalCount, Count, I: Integer;
begin
  Points := TObjectList<TPoint>.Create;
  try
    with TBinaryReader.Create(FileName) do
    try
      TotalCount := ReadInteger;
      SetLength(PointsBuffer, Min(TotalCount, MAX_BUFFER_SIZE));
      Points.Capacity := TotalCount;
      while TotalCount > 0 do
      begin
        Count := Min(TotalCount, Length(PointsBuffer));
        BaseStream.ReadBuffer(PointsBuffer[0], SizeOf(PointsBuffer[0]) * Count);
        Dec(TotalCount, Count);
        for I := 0 to Count - 1 do
          Points.Add(TPoint.Create(PointsBuffer[I].X, PointsBuffer[I].Y, PointsBuffer[I].Z));
      end;
    finally
      Free;
    end;
  finally
    Points.Free;
  end;
end;


Это сообщение отредактировал(а) Qu1nt - 20.4.2012, 22:22
PM MAIL   Вверх
Freimaks
Дата 21.4.2012, 07:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 23.4.2011

Репутация: нет
Всего: нет



Да, я сначала пытался просто Position и Size определять до входа в цикл чтения файла - прирост был.
Но больше всего помогло чтение файла за один раз, а потом циклом раскидывание его в Dictionary.
Выглядит вот так (кусок кода):
Код

procedure ReadBinPointsWithRecord(const FileName: String);
var i:integer; Pair:Tpair;
begin
Dictionary := TDictionary<TPair,TBinPoints>.Create;
with TBinaryReader.Create(FileName) do
try
BaseStream.Read(BinHeader, SizeOf(BinHeader));
OldPointCount:=BinHeader.PntCnt;
if (BinHeader.Time>0) and (BinHeader.Color=0) then
begin
SetLength(RPointsTimeArray,BinHeader.PntCnt); //задаем длину массива (RPointsTimeArray array of RPointsTime), равную количеству точек
BaseStream.Read(RPointsTimeArray[0], BinHeader.PntCnt*SizeOf(TRPointsTime)); //читаем файл за один раз
for i := 0 to BinHeader.PntCnt-1 do
begin
BinPoints:=TBinPoints.Create(
RPointsTimeArray[i].PointCoordX,
RPointsTimeArray[i].PointCoordY,
RPointsTimeArray[i].PointCoordZ,
RPointsTimeArray[i].PointCode,
RPointsTimeArray[i].PointEcho,
RPointsTimeArray[i].PointFlag,
RPointsTimeArray[i].PointMark,
RPointsTimeArray[i].PointLine,
RPointsTimeArray[i].PointInt,
RPointsTimeArray[i].PointTime);
if (Form1.RadioGroup1.ItemIndex=0) or (Form1.RadioGroup1.ItemIndex=1)  then
begin
Pair.PointCoordX:=BinPoints.PointCoordX;
Pair.PointCoordY:=BinPoints.PointCoordY;
Pair.PointCoordZ:=BinPoints.PointCoordZ;
Pair.PointTime:=BinPoints.PointTime;
end
else
if Form1.RadioGroup1.ItemIndex=2 then
begin
Pair.PointCoordX:=BinPoints.PointCoordX;
Pair.PointCoordY:=BinPoints.PointCoordY;
Pair.PointCoordZ:=BinPoints.PointCoordZ;
Pair.PointTime:=BinPoints.PointTime;
Pair.PointCode:=BinPoints.PointCode;
end;
Dictionary.AddOrSetValue(Pair, BinPoints);
end;
RPointsTimeArray:=nil;
end

Чтение происходит очень быстро - гораздо меньше секунды. Обработка тоже быстро проходит, запись... ну тут еще не сравнивал, пока не до нее - главное пишет правильно.
Пока не могу избавиться от двух проблем:
1. Жрет много памяти - это и логично, сначала файл в оперативку, потом дублируем его в Dictionary так еще и с ключем, состоящим из львиной доли файла. Обойти большой ключ проблематично. Но Вы говорили, что можно в качестве значений давать не сами значений класса, а лишь указатель на него. Как это сделать и как происходит удаление самих данных класса, я вообще понять не могу...
2. После отработки каждого файла в оперативке остается большое количество данных. И это не смотря на то, что я делаю обнуление массива RPointsTimeArray:=nil;, так еще и в конце обработки каждого файла делаю Dictionary.Free.
Статистика такая: подаем файл 120Мб, в оперативке максимальное потребление за время обработки примерно 550Мб, после завершения обработки остается 212Мб. Обработка (без записи) занимает время в в среднем 4200 мсек.
PM MAIL   Вверх
Qu1nt
Дата 21.4.2012, 10:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 602
Регистрация: 13.1.2007

Репутация: 22
Всего: 50



В общем я не знаю, что тебе сказать. Я говорю как нужно делать, привожу примеры, а ты пишешь по своему.
Подведем итог.
Не нужно весь файл в память грузить. Если бы ты запустил мой пример, увидел бы, что ~10 000 оптимальный размер буфера и его увеличение прироста не дает.
Не нужно использовать поле значения в TDictionary. Это отнимает лишнюю память.
Нужно понять разницу между TList/TObjectList, TDictionary/TObjectDictionary.
Нужно научиться форматировать код.
Нужно избавиться от глобальных переменных в пользу ООП.
PM MAIL   Вверх
Freimaks
Дата 21.4.2012, 10:34 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 23.4.2011

Репутация: нет
Всего: нет



Попробую переделать. Буду учить матчасть...
PM MAIL   Вверх
Freimaks
Дата 27.4.2012, 10:20 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 31
Регистрация: 23.4.2011

Репутация: нет
Всего: нет



Все сделал как советовали - действительно так лучше. Пробовал с разным размером буфера при считывании - да, после 10000 прироста нет (если и есть то он незначительный).
Переделал таким же макаром и запись, единственное при записи я использую буфер большего размера - 1 000 000 записей, дальше прироста нет, меньше - скорость записи падает.
Вроде бы щас написал все алгоритмы (сделал даже переброс точек в другой класс при нахождении дубликатов).
Все работает, но есть одно но, исправить которое наверно и невозможно. Это скорость самой обработки.
Сейчас у меня такой расклад: файл 240 Мб., 10506680 точек (все сдвоенные). Обработка от начала и до конца занимает 27815 мсек, из которых на саму обработку (удаление дубликатов) уходит 11482 мсек. Остальное сжирается записью и чтением.
Примерное сравнение с аналогичной программой - мое творение работает раз в 10 медленнее.
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Delphi: Для новичков"
SnowyMetalFan
bemsPoseidon
Rrader

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Литературу по Дельфи обсуждаем здесь
  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь
  • 90% ответов на свои вопросы можно найти в DRKB (Delphi Russian Knowledge Base) - крупнейшем в рунете сборнике материалов по Дельфи


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Snowy, MetalFan, bems, Poseidon, Rrader.

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Delphi: Для новичков | Следующая тема »


 




[ Время генерации скрипта: 0.1668 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.