Ускорить поиск строки в массиве строк.

← →
Регулятор (2012-06-09 11:11) [0]

Есть обычный TList заполненный таким:

type TItem = record Data: Pointer; Name: string; end;

В Data какая-нибудь именнованая структура, класс или еще что.

Вопрос как быстро найти нужный элемент по ключу максимально быстро?
Сейчас это простой цикл со сравнением в лоб.

Слышал про некие хэши и черно-красные деревья.
Но я самоучка. Такие штуки не понимаю.

Объясните, пожалуйста.

← →
Ega23 © (2012-06-09 11:17) [1]

Сортируй по строкам при добавлении. И поиск дихотомией.

← →
Palladin © (2012-06-09 11:26) [2]

https://www.google.ru/search?client=opera&rls=ru&q=TDictionary&sourceid=opera&ie=utf-8&oe=utf-8&channel=suggest

← →
TUser © (2012-06-09 11:35) [3]

> Слышал про некие хэши и черно-красные деревья.
> Но я самоучка. Такие штуки не понимаю.

Нет препятствий самоучкам! Можно посмотреть, например, в книге

Ахо, Хопкрофт, Ульман. Структуры данных и алгоритмы.

← →
Дмитрий С © (2012-06-09 12:05) [4]

Или посмотреть реализацию метода TStringList.Find и Sort. Я всегда так делаю =))

← →
MBo © (2012-06-09 14:18) [5]

1. Модифицируется ли список, или заполняется один раз?
2. Какова средняя длина строк-ключей?

← →
Регулятор (2012-06-09 16:15) [6]

> Ega23 © (09.06.12 11:17) [1]
>
> Сортируй по строкам при добавлении.

По алфавиту или как?

> MBo © (09.06.12 14:18) [5]
>
> 1. Модифицируется ли список, или заполняется один раз?
> 2. Какова средняя длина строк-ключей?

1. Заполняется по надобности.
Т.е. может сейчас добавим 10 записей, потом еще сколько-то.
Обычно записи не удаляются.
Если удаляются, то все зараз.

2. Обычно не больше 15 символов.

← →
Ega23 © (2012-06-09 18:01) [7]

> По алфавиту или как?

Ну уж сам критерий подбирай, я тебе тут не советчик

← →
TUser © (2012-06-09 18:08) [8]

> 10 записей

При таких размерах оптимизация не нужна.

← →
Kerk © (2012-06-09 18:15) [9]

> TUser © (09.06.12 18:08) [8]
>
> > 10 записей
>
> При таких размерах оптимизация не нужна.

Это не нанотехнологично (с)
:)

← →
Регулятор (2012-06-09 18:49) [10]

> TUser © (09.06.12 18:08) [8]
>
> > 10 записей
>
> При таких размерах оптимизация не нужна.

О да, всунуть 10 записей в сортированный блоб из пару лярдов элементов, нафиг оптимизировать? :)

ЗЫ: по сабжу, наиболее оптимально будет использовать сортированный двунаправленный список.
Т.е. грубо работаем со структурой:

TItem = record Data: Pointer; Name: string; PreviosItemIndex, NextItemIndex: Integer; end; TItems = array of TItem;
Поиск дихотомией, объединение одинарным проходом двумя курсорами.

> Есть обычный TList заполненный таким:
> type > TItem = record > Data: Pointer; > Name: string; > end;

пусть станет обычным TStringList без record, заполненным объектами, строкой с указателем...
там есть сортировка, и быстрый поиск.

Раз набор данных модифицируется, то статическую структуру данных использовать нехорошо, и подойдет любая реализация словаря (Dictionary, Map) - сбалансированные деревья (RB, AVL), хэш-таблицы, trie. Например - THashedStringList из inifiles

> Регулятор (09.06.12 18:49) [10]
>
> > TUser © (09.06.12 18:08) [8]
> >
> >
> > > 10 записей
> >
> > При таких размерах оптимизация не нужна.
> >
>
>
> 100
>
>

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

Ускорить поиск строки в массиве строк. Найти похожие ветки