Ты плохо изучил возможности TStringList Ставишь Sorted := True сразу после создания объекта(и до добавления данных) и ищешь с помощью IndexOf(тут искомая строка). Если вернет - 1 значит этой строки нет в списке. В отсортированном списке эта функция использует алгоритм бинарного поиска => намного быстрее перебора как у тебя ЗЫ а какие собственно объемы?
ща попробую. объемы - ну, от 100к строк уже начинает заметно тормозить. upd: ох шикарно стало спасибо большое!
1n0y, альтернатива двоичному поиску - поиск в таблице на дельфи перенести пять минут Code: K&R 6.6 Просмотр таблиц В этом параграфе, чтобы проиллюстрировать новые аспекты применения структур, мы напишем ядро пакета программ, осуществляющих вставку элементов в таблицы и их поиск внутри таблиц. Этот пакет - типичный набор программ, с помощью которых работают с таблицами имен в любом макропроцессоре или компиляторе. Рассмотрим, например, инструкцию #define. Когда встречается строка вида #define IN 1 имя IN и замещающий его текст 1 должны запоминаться в таблице. Если затем имя IN встретится в инструкции, например в state = IN; это должно быть заменено на 1. Существуют две программы, манипулирующие с именами и замещающими их текстами. Это install(s,t), которая записывает имя s и замещающий его текст t в таблицу, где s и t - строки, и lookup(s), осуществляющая поиск s в таблице и возвращающая указатель на место, где имя s было найдено, или NULL, если s в таблице не оказалось. Алгоритм основан на хэш-поиске: поступающее имя свертывается в неотрицательное число (хэш-код), которое затем используется в качестве индекса в массиве указателей. Каждый элемент этого массива является указателем на начало связанного списка блоков, описывающих имена с данным хэш-кодом. Если элемент массива равен NULL, это значит, что имен с соответствующим хэш-кодом нет. Блок в списке - это структура, содержащая указатели на имя, на замещающий текст и на следующий блок в списке; значение NULL в указателе на следующий блок означает конец списка. struct nlist { /* элемент таблицы */ struct nlist *next; /* указатель на следующий элемент */ char *name; /* определенное имя */ char *defn; /* замещающий текст */ }; А вот как записывается определение массива указателей: #define HASHSIZE 101 static struct nlist *hashtab[HASHSIZE]; /* таблица указателей */ Функция хэширования, используемая в lookup и install, суммирует коды символов в строке и в качестве результата выдаст остаток от деления полученной суммы на размер массива указателей. Это не самая лучшая функция хэширования, но достаточно лаконичная и эффективная. /* hash: получает хэш-код для строки s */ unsigned hash(char *s) { unsigned hashval; for (hashval = 0; *s != '\0'; s++) hashval = *s + 31 * hashval; return hashval % HASHSIZE; } Беззнаковая арифметика гарантирует, что хэш-код будет неотрицательным. Хэширование порождает стартовый индекс для массива hashtab; если соответствующая строка в таблице есть, она может быть обнаружена только в списке блоков, на начало которого указывает элемент массива hashtab с этим индексом. Поиск осуществляется с помощью lookup. Если lookup находит элемент с заданной строкой, то возвращает указатель на нее, если не находит, то возвращает NULL. /* lookup: ищет s */ struct nlist *lookup(char *s) { struct nlist *np; for (np = hashtab[hash(s)]; np != NULL; np = np->next) if (strcmp(s, np->name) == 0) return np; /* нашли */ return NULL; /* не нашли */ } В for-цикле функции lookup для просмотра списка используется стандартная конструкция for (ptr = head; ptr != NULL; ptr = ptr->next) ... Функция install обращается к lookup, чтобы определить, имеется ли уже вставляемое имя. Если это так, то старое определение будет заменено новым. В противном случае будет образован новый элемент. Если запрос памяти для нового элемента не может быть удовлетворен, функция install выдает NULL. struct nlist *lookup(char *); char *strdup(char *); /* install: заносит имя и текст (name, defn) в таблицу */ struct nlist *install(char *name, char *defn) { struct nlist *np; unsigned hashval; if ((np = lookup(name)) == NULL) { /* не найден */ np = (struct nlist *) malloc(sizeof(*np)); if (np == NULL || (np->name = strdup(name)) == NULL) return NULL; hashval = hash(name); np->next = hashtab[hashval]; hashtab[hashval] = np; } else /* уже имеется */ free((void *) np->defn); /* освобождаем прежний defn */ if ((np->defn = strdup(defn)) == NULL) return NULL; return np; }
1n0y, сделай связанный список, состоящий из указателей на структуру из 8 байт : 4 байт - ID 4 байт - указатель на след. структуру. И все, единственно такими маленькими кусочками будет дефрагментироваться память, ну если тебе не важна скорость, то не суть.
А то, что памяти раза в 3 меньше будет использоваться - это не преимущество? Все уже изобретено, TList называется. Метод IndexOf класса TStringList так и работает Что быстрее - сравнить 2 строки по 8 символов или 2 восьмизначных числа?
Не подумал об этом. При поиске строки в отсортированном TStringList скорость будет такой же, как при поиске числа в TList. Остается только преимущество в объеме используемой памяти.
В современных версиях дельфи есть решение намного лучше: TList<Integer> Для чисел реализован дефолтный компаратор. И расходов памяти лишних не будет, и сравнение чисел работает на порядок быстрее чем строк. Не стал об этом сразу писать, ибо тут у большинства стоит дельфи 7, и про дженерики тут слыхом не слыхивали. Если ТСу надо и у него модерновая дельфи то могу написать пример как лучше хранить числа.
я конечно понимаю что 7 пожалуй самая удачная версия, но может быть пора с нее слазить? Как минимум ради Generiс коллекций...
2 W!z@rD D7 (2002 год выпуска) стала на столько легендарной как и WinXP (2001 год выпуска). Видимо в те года делали продукты на века )) На хабре было обсуждение D7 и более новых версий. И почти все склонны к тому, что конкуренцию для D7 может составить только Delphi 2010
Ок, она грузицца на 5 сек. дольше, но сокращает время на разработку раза в два наверное. А если в среду ставить эксперты/визарды/плагины то разница по времени загрузки и вовсе становится неощутимой.
Jingo Bo, M_script! Можете примерно рассказать как в данной задаче юзать тлист? погуглил, но толком нечего и не понял. заранее благадарю стринглист-то хорош, только вот когда блек >1 ляма начинаются ошибки out of memory
1n0y, приводить пример не буду, т.к. очередной велосипед, при том при всем писать с сортировкой и организацией списка строк 200 не хочется. Гуглить надо "Delphi связанный список", элементом которого является запись из Cardinal числа. Еще хочу посоветовать хранить не только начальный, но и конечный элемент списка, для того что бы определение по индексу было быстрее. Допустим есть у нас список из 100 элементов, нужен 80-ый, что бы до него добраться - быстрее с конечного спускаться, чем с начального подниматься. И второй совет - выделяй память блоками, а не по одному элементу, так память будет меньше дефрагментироваться, конечно тут придется подумать как лучше это реализовать.
спасибо! погуглив, решил всёже отложить это дело. допилил немного блеклист из стринлиста - теперь даже с >2 лямами работает стабильно. посмотрим как пойдет
Нашел простое и эффективное решение для блэк-листа ВК - массив битов. Огромная скорость и список ID любого объема взамен на 16 метров памяти. Пример: PHP: long black[4 * 1024 * 1024]; //--------------------------------------------------------------------------- bool is_black(long id) { return ( black[id/32] & (1 << id%32) ) ? true : false; } //--------------------------------------------------------------------------- void add_black(long id) { black[id/32] |= (1 << id%32); } //--------------------------------------------------------------------------- int main() { memset(&black[0], 4 * 4 * 1024 * 1024, 0); char buf[256] = {0}; FILE* f = fopen("black.txt", "r"); while(fgets(buf, 255, f)) add_black(atol(buf)); long id = 0; cin >> id; cout << is_black(id); return 0; } //---------------------------------------------------------------------------
