Всем привет!

Опишу свою проблему, но сразу поясню - программированием давно не занимался (последний раз года полтора назад писал прогу для работы с xls и csv файлами).

Суть проблемы: есть массив данных в достаточно специфическом формате. Формат называется bin, используется для хранения данных лазерного сканирования в программе TerraScan (также las, fastbin и т.д.).

Каждая точка имеет достаточно большое количество параметров, но интересует всего несколько, а именно принадлежность к классу, отметка времени и координаты XYZ.

Что хочу реализовать - поиск одинаковых точек (одинаковые XYZ, например). Соответственно весь этот массив надо сортировать. Сортировка каким-нибудь пузырьком (воспоминания из универа) не подходит, т.к. массив может быть очень большой - десятки и сотни миллионов точек.
Не могли бы спецы подсказать - какой алгоритм позволит наиболее быстро обрабатывать такой большой массив данных.

Заранее огромное спасибо!!!!

Что в конечном итоге нужно сделать с этими точками? Просто узнать количество одинаковых, или после сортировки (кстати, не уверен, что она вообще сможет отработать) проанализировать дополнительные параметры каждой из одинаковых?

есть Быстрая сортировка и Сортировка слиянием

Вообще предполагается написание проги, которая будет удалять точки с одинаковыми параметрами (например с одинаковыми координатами). Т.е. надо найти все точки с одинаковыми координатами и оставить только одну.

(имхо) любые сортировки в памяти не актуальны с учетом 

С учетом кучи параметров каждой точки, это выйдет (как минимум) не одна сотня мегабайт. Слишком велика вероятность наткнуться на EOutOfMemory, и даже если (каким-то чудом) нет - бедный файл подкачки.

Да действительно, эти файлы достаточно велики по объему. По сути речь идет об обработке файлов от 10 до 500 мегабайт.

Хеш-таблица.

что с ней делать?

Pretorian, данные из файла загрузить в хеш-таблицу. Дубликаты ликвидируются автоматически.

Qu1nt, хотел предложить подобный вариант, но думал, что структура которая отсекает двойников называется множеством (Set)

Это сообщение отредактировал(а) Pretorian - 13.4.2012, 13:29

Сижу, читаю. Буду пытаться это реализовать. Думаю сначала на маленьком примере из 100 точек попробую. Мне самому даже интересно не столько 100% реализация задуманного (все равно делаю можно сказать для себя), сколько понимаю того как это можно реализовать, а там уже подгоню и производительность.

Pretorian, множества обычно реализуют на основе хеш-таблиц.
Dementor, используй TDictionary из Generics.Collections.

Осмелюсь задать еще один вопрос.
Я как-то вообще с конца пошел...
А вопрос в следующем - как открыть файл с известной структурой?
Каким надо инструментом для этого пользоваться (предполагая работу с N числом файлов)? Соответственно, чтобы потом передать считанную инфу в TDictionary.
Могу привести структуру файла (Scan binary 16 bit line):

Если объясните хотя бы примерно - буду очень благодарен.

Это сообщение отредактировал(а) Dementor - 13.4.2012, 14:46

С помощью TBinaryReader читай только необходимые тебе поля.

Посидел, кое-что написал. Есть пара непонятных моментов, из-за которых все рушится. Пока я пытаюсь хотя бы считать данные из раздела Header (по сути мне от туда необходимо только одно поле):
Итак я объявляю все переменные:

Далее просто для того, чтобы понять чего я вообще получаю при чтении на выход я не только считываю, но и пишу все в memo

for ifiles:= 0 to ifilesall-1 do - отвечает за работу если открыто несколько файлов (указание на файлы идет через OpenDialog).
Что получаю на выходе:

До строки XYZ(далее у меня какой-то крестик в memo) все верно - как в документации к файлу.
Строка "XYZ(какой-то крестик)" по сути должна иметь вид "CXYZ". А далее видимо все рушится из-за неправильной отработки этой части файла (а может и нет...).
И это я не дошел даже до рездела с точками (где структура еще хлеще).
Подскажите, чего я делаю не так???

В общем случае можно выделить два подхода:
Частичное описание структуры. Целесообразно использовать для экономии памяти. 

Полное описание структуры. 

В твоём случае ошибка заключается в том, что с помощью ReadString можно читать только те строки, которые записаны через WriteString. В этих методах сначала читается/записывается размер строки, а только потом данные.

Да, предложенный способ оказался рабочим - Header считывается без проблем. Щас немного доработаю и попробую также считать точки. Хотя конечно далеко не все мне понятно в плане работы TBinaryReader

Тут два способа. Первый лучше применить к точкам, второй - к заголовку.

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

P.S. а за что отвечает в процедуре Output: TStrings??? Т.е. понятно, что позволяет использовать Output.Append(Format('Time: %d', [ReadInteger]));, но как его описывать при вызове процедуры?

В точках конечно структура сложнее


Это сообщение отредактировал(а) Freimaks - 14.4.2012, 13:32

Например

АААА, все понял. Я просто удалил его, понимая что он не очень важен, но не понимая, что он реально делает. Теперь усе понял!!!

Недостаточно информации. Неясно как определять наличие того или иного атрибута.

Да, инфы мало. Сам сижу думаю, а как определить что есть какой-то атрибут из необязательных или его нет. В принципе многие из них по умолчанию есть, но от раза к разу могут добавляться или уходить...

Хм, а вот я нашел такие форматы:

http://www.scribd.com/doc/88768096/282/Ter...an-binary-files

Я инфу беру тоже из мануала к TerraScan-y.
Ту портянку с кучей параметров, их обязательностью и т.п. я взял от туда же.
Я попробую у одного программера выудить инфу о том как он читает эти файлы - там помоему как-то через сишные библиотеки делается.
Просто че-то это какая-то морока.
Просто почти весь софт для этой отрасли пишется на С++, поэтому для Delphi приходится изобретать колесо.
Если будет инфа и решения - я обязательно напишу, дабы не потерялось - может кому пригодится.

Сама точка в этом формате, действительно может иметь только обязательные параметры, но есть еще куча необязательных - софт их должен воспринимать если они есть.

Это сообщение отредактировал(а) Freimaks - 14.4.2012, 16:05

Немного поколдовав получилось считать инфу по точкам:
1. Описание 2-х типов:

В принципе надо будет еще расширить, так как опционально пишется еще цвет ТЛС.
Процедуры без изменений:


Все читается без проблем.

Теперь осталось все это засунуть в TDicrionary

А не могли бы привести пример как это сделать???
Посмотрев вот на это http://docwiki.embarcadero.com/CodeSamples...ionary_(Delphi) я так и не понял как мне мои точки засунуть в эту таблицу.
И сразу задам еще вопрос - как инструмент поступает с одинаковыми значениями?
Т.е. по идеи не хотелось бы, чтобы он сразу удалял дубли...

Попробовал вот так:

Далее в процедуре:

Выдает ошибку Access violation at address....

Это сообщение отредактировал(а) Freimaks - 16.4.2012, 16:48

А какое поведение тебе нужно?

Прежде чем работать с объектом, его нужно создать. И не забыть уничтожить.

Я рассматриваю несколько вариантов работы программы:
1. Анализ данных на наличие дублей, при этом пользователь получает отчет типа да\нет
2. Поиск дублей по всем точкам и действия над дублями (удаление или изменение параметра класс)
3. Поиск дублей для точек в определенных классах


А как это сделать? Я просто в этом уже не разбираюсь вообще.
В Uses я добавил Generics.Collections и больше ничего не изменял

Как я понимаю хэш-таблицы, в том числе и TDictionary, не позволяют хранить дубликаты.
А насколько логично использовать массив в данном случае???

Да, можно использовать шаблонный TList.

Да, я его и взял.
Делаю так:
1. Объявляю класс

2. Далее описываю Конструктор для класса Point

3. Ну и в заключении в процедуру чтения добавил заполнение Point

Теперь буду писать обработку инфы в TList

Вообще с TList получается как-то громоздко на мой взгляд.

Узнал такую вещь - в прогах на C++ данные закачиваются в память в виде динамического массива. Т.е. - каждая точка это структура (в делфи - record), а весь бин - это динамический массив структур.

Вопрос - как описать массив из record в моем случае???

Сделал вот так


далее в переменных прописал


И далее в процедуре чтения:


Не знаю на сколько правильно, но ошибок не выдает...

Это сообщение отредактировал(а) Freimaks - 18.4.2012, 11:02

Я бы использовал классы. Ведь, тебе все-равно нужно будет прогонять все точки через TDictionary для поиска дубликатов. В случае с классами будет копироваться только указатель, иначе — объект.

И еще - как установить этот компонент??? Я всегда работал только со встроенными компонентами и об установке сторонних никогда не слышал.
Щас читаю http://docs.embarcadero.com/products/rad_s...collections.pdf
Пока мало что понятно

Это сообщение отредактировал(а) Freimaks - 18.4.2012, 14:42

Вечером. После работы и до футбола 

@ Добавлено
TDictionary — стандартный компонент начиная c Delphi 2009. Я надеюсь у тебя не Delphi 7?

Это сообщение отредактировал(а) Qu1nt - 18.4.2012, 14:46

Если честно, то у меня установлено Delphi XE2...

Отлично. Это самая последняя версия на данный момент. Для того, чтобы его использовать достаточно подключить соответствующий модуль.

А, все завелось!!! Я просто не туда прописал   Dictionary:TDictionary<Integer, Integer>; поэтому и не пахало!!!
А я уже начал гугл рыть на предмет установки этой примочки...

Ну в общем вот пока что смог сделать с этим TDictionary:

Потом просто проверил работает ли

Выводит нужное число, т.е. скока было в файле. Все супер. Разбираюсь дальше.

Добавлено через 6 минут и 26 секунд
Прав ли я считая, что Key в Dictionary.Add и есть тот самый уникальный ключ, который показывает есть такая запись или нет?
Если да, то как мне этот ключ получить? Наверно нужно в качестве ключа использовать что-то типа суммы MD5???
Если то что написал - бред, не пинайте! Пока только это пришло в голову...

Сделал как и советовали классами (пока только один завел, тестовый). И перестало работать.
Вот чего делаю:
Завожу класс

Делаю конструктор:

В переменных добавляю новое значение

Ну и собственно процедура чтения:


В итоге при считывании выдает ошибку Access violation at address 0053c49d in module...

Заменил TBinPoints_time = class(TObject) на TBinPoints_time = packed record и все заработало

Появился еще один вопрос. А как после загрузки в TDictionary вернуть все ее содержимое? Т.е. мне же потом надо все переписать в новый файл.
Процедуру записи я написал, но как достать то, что лежит в TDictionary я так и не понял (отдельными полями я понял как достать).
Т.е. что надо указывать в записи BaseStream.Write(???????????????, SizeOf(TBinPoints_time));


Сделал вот так, на сколько правильно я не знаю, но работает


Это сообщение отредактировал(а) Freimaks - 18.4.2012, 19:54

Ты не понимаешь разницы между record, packed record и class. Лучше чем в книге я тебе не объясню.

Да, в теории я не силен - буду читать щас

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

И далее в качестве Key использовал BinPoints.PointCode (типа класс) и в итоге у меня в TDictionary оставалось количество записей=количеству разных классов.
Потом в качестве Key попробовал указывать MD5 от строки из координат... работает конечно - но долго до невозможности.
В общем пока остались вопросы по Key в TDictionary.

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

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

К сожалению, стандартного шаблонного множества в Delphi нет, как и аналога С++ std::multimap. Поэтому для экономии памяти я бы использовал в TDictionary только поле ключа. И в зависимости от задачи менял только компаратор.

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

Чтение этого файла размеров в 53.3 мегабайта занимает около 30 секунд... если не больше.
Можно как-то ускорить. Хотя бы куда копать не подскажете?

Как ситуация меняется, если убрать взаимодействие с пользовательским интерфейсом? Убери Application.ProcessMessages и ProgressBar из цикла.

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

RPointsTime - это packed record.

Хорошо, в таком случае нужно читать блочно. Попробуй за раз читать несколько тысяч точек. 

А не подскажите, как это сделать???

Я понял как делать!!! Ща усе сделаю 

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


Это сообщение отредактировал(а) Qu1nt - 20.4.2012, 22:22

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

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

В общем я не знаю, что тебе сказать. Я говорю как нужно делать, привожу примеры, а ты пишешь по своему.
Подведем итог.
Не нужно весь файл в память грузить. Если бы ты запустил мой пример, увидел бы, что ~10 000 оптимальный размер буфера и его увеличение прироста не дает.
Не нужно использовать поле значения в TDictionary. Это отнимает лишнюю память.
Нужно понять разницу между TList/TObjectList, TDictionary/TObjectDictionary.
Нужно научиться форматировать код.
Нужно избавиться от глобальных переменных в пользу ООП.

Попробую переделать. Буду учить матчасть...

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

Показывай весь проект.

Сразу извиняюсь если что-то написано не грамотно, но я так сказать пока только учусь.
Выкладываю процедуры чтения и записи (все остальное это просто обращение к ним и в зависимости от результата формирование отчетов и т.п.
Процедура чтения (всего три варианта, т.к. три вида файлов):

2. Процедура записи

3. Процедура формирования ключа

4. Процедура когда нужно найти дубли, но оставить четко один класс. Написано очень тупо, но при других вариантах я получал всякую гадость

Вот все что получилось.
Сравнение с другой программой проводил, но это конечно глупо. Как она работает я не в курсе, могу лишь сказать что там делается некая сортировка. Памяти она потребляет гораздо меньше (видимо ключи там не хранятся).
Я на досуге пытался почитать Кнута, но дается пока с трудом...

Зачем тебе строковой ключ? Возьми за основу мой код.

Да, Вы как всегда правы. Замена строкового ключа на просто числовой дает во-первых более чем трехкратное повышение производительности, так еще и позволяет уменьшить потребление памяти примерно в три раза. В итоге получается, что полное время обработки того же файла идет 9033 мсек, а именно обработка занимает 3291 мсек (круто!!!!). Но это так сказать грубо.
Я просто немного недопонимаю пример и как его применить на все 100%.
В вашем примере все организовано на классах, где сравнение идет с помощью Equals и GetHashCode (если я все правильно понял из прочтенной теории). У меня же все сформировано на записях (я если честно так и не понял преимущества использования классов).
Соответственно для формирования ключа я просто подсунул вот это:

И соответственно этот подход не дает уникального ключа для достаточно большого числа точек.
Правильно ли я понимаю, что все это будет работать только при условии использования классов и их методов Equals и GetHashCode.
В литературе встретил подобное вычисление HashCode, правда с другими простыми числами.