Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2013.03.22;
Скачать: CL | DM;

Вниз

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

 
Регулятор   (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 записей
>
> При таких размерах оптимизация не нужна.
>


100


 
Rouse_ ©   (2012-06-09 19:00) [11]


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

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

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

TItem = record
   Data: Pointer;
   Name: string;
   PreviosItemIndex, NextItemIndex: Integer;
end;
TItems = array of TItem;

Поиск дихотомией, объединение одинарным проходом двумя курсорами.


 
sniknik ©   (2012-06-09 19:18) [12]

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


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


 
MBo ©   (2012-06-09 19:21) [13]

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


 
TUser ©   (2012-06-09 23:27) [14]


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

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



Страницы: 1 вся ветка

Текущий архив: 2013.03.22;
Скачать: CL | DM;

Наверх




Память: 0.5 MB
Время: 0.353 c
15-1346911110
AV
2012-09-06 09:58
2013.03.22
Программистом я б пошел.. Пусть меня научат!


15-1329510280
istok20
2012-02-18 00:24
2013.03.22
Перехват gtalk и gmail..


2-1346832461
Levran
2012-09-05 12:07
2013.03.22
порядок вывода записей


15-1329458550
coward
2012-02-17 10:02
2013.03.22
FreeSoft AV


2-1329850454
Аццкий
2012-02-21 22:54
2013.03.22
вопрос про чар