Всем привет!

Опишу свою проблему, но сразу поясню - программированием давно не занимался (последний раз года полтора назад писал прогу для работы с 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". А далее видимо все рушится из-за неправильной отработки этой части файла (а может и нет...).
И это я не дошел даже до рездела с точками (где структура еще хлеще).
Подскажите, чего я делаю не так???