Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Delphi: Для новичков > Поиск дубликатов в TTreeView

Автор: mr.Anderson 22.8.2007, 13:46

Задача следующая.

В процессе анализа текста у меня формируется дерево (контрол TTreeView). В нем три корневых раздела. В каждый из корневых узлов по мере анализа вносятся нужные подразделы. Проблема в том, что нельзя, чтобы в корневой узел вносился подраздел, КОТОРЫЙ ТАМ УЖЕ ЕСТЬ, короче, нельзя дублировать подразделы. Но!

Для поиска дубликатов приходится обходить ВСЕ подразделы данного корневого узла, и, как вы понимаете, это сильно увеличивает время построения дерева - чем больше дерево - тем дольше работа (так как тем с большим количеством подразделов приходится проводить сравнение).

Я никак не могу придумать алгоритм быстрого поиска дубликатов в корневом разделе дерева. Вот это и есть основная задача. Мой алгоритм "прямой" и прет напролом, что добавляет целых 2-3 минуты ко времени анализа: он просто циклически обходит все подразделы. Это самый простой и самый длительный по времени алгоритм.

P.S. Хочу заметить, что дерево не бинарное, то есть в каждом из трех корневых разделов может быть любое количество подразделов. А вот у подразделов дочерних нодов уже нет - т.е. дерево двухуровневое: корень - подразделы.

Автор: dumb 22.8.2007, 14:02

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

хотя, скорее всего, основные тормоза в строковых сравнениях - если те же хэши заголовков элементов класть в item.Data, и, пробегая по цепочке элементов, сравнивать хэш нового эл-та с item.Data, то будет гораздо веселей...

Автор: mr.Anderson 22.8.2007, 14:31

А примерчик можете привести? Data - это поле типа Pointer. А в DRKB я нашел реализацию CRC32-функции, возвращающую Integer. Плюс в нее передаются непонятные параметры типа IniCRC: Integer.

Автор: dumb 22.8.2007, 15:57

второй вариант(т.е. без массивов хэшей):

Код


procedure TForm1.Button1Click(Sender: TObject);
var
  s: String;
  dup: Boolean;
  crc: Dword;
  item: TTreeNode;
begin
  s := Edit1.Text;
  if s = '' then exit;
  crc := CRC32(-1, s);
  dup := false;
  item := TreeView1.Items.GetFirstNode;
  while item <> nil do
  begin
    if crc = Dword(item.Data) then begin
      dup := true;
      break;
    end;
    item := item.GetNext;
  end;
  if not dup then
    TreeView1.Items.AddChildObject(nil, s, Pointer(crc));
end;

Автор: MetalFan 22.8.2007, 16:13

посмотри в сторону VirtualTreeView. оно в разы быстрее стандартного работает, если правильно его применить)

Автор: mr.Anderson 22.8.2007, 16:59

dumb, благодарю!

MetalFan, спасибо, поищу данный контрол. Пока нарыл описание, очень обнадеживает, попробую работать с ним.