Форум: "Основная";
Текущий архив: 2006.09.10;
Скачать: [xml.tar.bz2];
Вниз
Анализ строк в TStringList Найти похожие ветки
← →
RedLeo (2006-07-26 17:39) [0]Есть такая проблема:
Существует список(TStringList) примерно из 300000 строк следующего вида:
имя=значение
как быстро создать на его основе 2 списка, один из которых составляется по следующему правилу: Если элемент с именем не существует в результирующем списке, то добавить его в противном случае добавить только значение. " список представляет собой только список имен результирующего.
Пример:
Исходный список:
Имя1=1
Имя2=2
Имя3=3
Имя1=5
Имя2=6
В результате получаются 2 списка:
Первый:
Имя1=1 5
Имя2=2 6
Имя3=3
Второй:
Имя1
Имя2
Имя3
Пытался решить задачу простым перебором строк в списке - получилось очень долго (8 секуед на 100 записей)
Вот, мое решение:
. . .
if source.Count>0 then
for i:=0 to source.Count-1 do
begin
end;
s:=source.Names[i];
if outList.Values[s]="" then begin
outList.add(source[j]);
nameList.Add(ansiLowerCase(s))
end else
outList.Values[s]:=outList.Values[s]+" "+ source.ValueFromIndex[i];
end;
. . .
Пожалуйста, помогите оптимизировать код и ускорить данный процесс.
← →
vain © (2006-07-26 18:19) [1]Надо отсортировать исходный список по полю Name, тогда в списке сначала будут все строки с ИМЯ1, потом с ИМЯ2... и т. д. Сложность quick sort"а - N*log2(N). Да ещё умнож это выражение на среднюю длину строки L. Вот и получается: L*N*log2(N) действий. (Придётся тебе вспомнить быстую сортировку) это примерно 5"500"000*L. Мне кажется, ничего быстрее придумать нельзя.
← →
Джо © (2006-07-26 18:25) [2]"Малой кровью" можно немного ускорить процесс, использовав THashedStringList (IniFiles, кажется) вместо TStringList. Там для сравнения используются хэши строк. Естественно, придется смириться с увеличением накладных расходов на память.
← →
Джо © (2006-07-26 18:26) [3]Разумеется, нужно будет использовать IndexOf для поиска существующего значения.
← →
jack128 © (2006-07-26 18:26) [4]RedLeo (26.07.06 17:39)
откажись от использования свойства Values - это вечный тормоз.
← →
Ketmar © (2006-07-26 19:04) [5]предлагаю использовать другую структуру для хранения данных. например, Red-Black Tree, в котором хранятся записи с некоторой информацией.
как? подумайте, намёк я дал.
← →
vain © (2006-07-26 19:10) [6]
> предлагаю использовать другую структуру
Что такое Red-Black Tree?
← →
default © (2006-07-26 19:13) [7]vain © (26.07.06 19:10) [6]
красно-чёрные деревья
сделай поиск
← →
Мефисто (2006-07-26 20:44) [8]
> Ketmar © (26.07.06 19:04) [5]
Ты еще на труды Дональда Кнута намекни :) Математики - вагон и маленькая тележка.
← →
tesseract © (2006-07-26 21:56) [9]> [5] Ketmar © (26.07.06 19:04)
лучше B-tree они лучше изучены.
← →
atruhin © (2006-07-27 00:17) [10]Если этот словарь твой, то лучше всего его отсортировать один раз, а далее загружать уже отсортированный.
Если нет, то или B-tree, или Hash таблицы. Готовых алгоритмов в сети масса.
И в любом случае отказаться от outList.Values и подобного, использую динамические записи.
← →
Ketmar © (2006-07-27 14:50) [11]>tesseract © (26.07.06 21:56) [9]
так не диссертация же нужна. а использование. я вот RBT использую не первый год -- нареканий никаких. %-)
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2006.09.10;
Скачать: [xml.tar.bz2];
Память: 0.47 MB
Время: 0.043 c
