| Dmitri |
 Отправлено: 22.02.2004, 19:18 |
|
admin@localhost
Группа: Модератор
Сообщений: 110
|
Подскажите, пожалуйста, как можно пробежаться по массиву строк типа "text1\r\ntext2\ntext3..." на наличие дубликатов между \r\n и удалить их, оставив только оригиналы? Не сравнивать же в цикле каждый i-ый элемент со всеми остальными элементами?
Очень важна скорость (объем обрабатываемой информации ~ 10 Mb).
Мне что-то говорили про hashset. How to use? В MSDN все кратко и непонятно.
Есть ли еще какие-либо альтернативные варианты?
|
|
| Admin |
| Отправлено: 22.02.2004, 22:43 |
|
Владимир
Группа: Администратор
Сообщений: 1190
|
Насчет скорости не знаю...
Можно попробовать запихнуть все строки в StringGrid
поставив свойство Sorted = true и Duplicates = dupIgnore
тогда повторяющиеся строки туда не добавятся.
Получите массив отсортированных уникальных строк.
| CODE |
// Имеем компонент pList типа TListBox
// загоняем в него неуникальные значения
void __fastcall TForm1::Button1Click(TObject *Sender)
{
pList->Items->Add("Plants");
pList->Items->Add("Animals");
pList->Items->Add("Minerals");
pList->Items->Add("Plants");
pList->Items->Add("Animals");
pList->Items->Add("Minerals");
pList->Items->Add("Plants");
pList->Items->Add("Animals");
pList->Items->Add("Minerals");
}
//---------------------------------------------------------------------------
// создаем массив строк TL типа TStringList
// отсортированный с уникальными значениями
// помещаем в него строки из pList — вставятся
// только уникальные — проверяем это
// с помощью LIstBox2
void __fastcall TForm1::Button2Click(TObject *Sender)
{
TStringList * TL = new TStringList;
TL->Sorted = true;
TL->Duplicates = dupIgnore;
for(int i=0; i<pList->Count; i++)
TL->Add(pList->Items->Strings[i]);
ListBox2->Items = TL;
delete TL;
}
//---------------------------------------------------------------------------
|
|
|
| Георгий |
| Отправлено: 22.02.2004, 22:53 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
hash таблицы мне кажутся не удачным решением — для поиска они очень хороши, но при постоянном добавлении элементов их эффективность обычно сильно падает.
предлагаю другие методы:
1:
можно использовать set — он вроде бы основан на би деревьях и значительно лучше подходит для отброса повторений при неизвестном числе входных данных.
консольная програмка, которая не показывает повторяющиеся элементы массива
| CODE | #include <set.h>
#include <string.h>
#include <fstream.h>
#include <iostream.h>
//---------------------------------------------------------------------------
char *TestArray[]={"qwe","asd","zxc","asd","123","321","qwe","ert"};
#pragma argsused
int main(int argc, char* argv[])
{
set <string, less<string> > ss;
//заполняем набор значениями
for (int i=0;i<sizeof(TestArray)/sizeof(TestArray[0]);i++)
ss.insert(TestArray[i]);
//выводим набор на экран
copy (ss.begin(), ss.end(), ostream_iterator<string>(cout, "\n"));
return 0;
}
//--------------------------------------------------------------------------- |
2:
если уже есть массив указателей на строки, то, на мой взгляд, самым быстрым будет отсортировать массив с помошью библиотечной функции qsort, а потом, линейно пробежаться и искать повторы — повторяющиеся элементы будут находиться рядом.
PS. 2-й метод по теоретическим оценкам в 2 раза медленнее 1го, но на практике он может оказаться быстрее за счёт своей простоты — отсутствуют какие либо операции отличные от сравнения т.е. нет ни выделения памяти, ни перестройки внутренней структуры. но у него есть ограничения — после добавления элемента требуется заново пересортировать массив, что в случае с set`ом происходит автоматически. |
|
| Dmitri |
| Отправлено: 22.02.2004, 23:00 |
|
admin@localhost
Группа: Модератор
Сообщений: 110
|
Владимир:
Я пишу консольную программу. Использование VCL нежелательно.
Георгий:
Спасибо за пример. Могли бы Вы пояснить строки:
#pragma argsused
set > ss;
copy (ss.begin(), ss.end(), ostream_iterator(cout, "\n"));
Отредактировано Dmitri — 23/02/2004, 02:26
|
|
| Георгий |
| Отправлено: 23.02.2004, 12:24 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
1
затыкает предупреждения, что не все аргументы функции используются в её теле.
2| CODE | | set <string, less<string> > ss |
объявляет переменную класса-шаблона set с использованием класса string и бинарной функции-шиблона less для класса string.
а если по простому, то создаётся набор (set) с операщией сравнения сделанной тоже по шаблону.
3| CODE | | copy (ss.begin(), ss.end(), ostream_iterator<string>(cout, "\n")); |
копирует элементы набора с первого по последний используя интератор-выходной поток созданный по шаблону для string.
2 и 3 — это должно быть описано в книжках посвящённых STL
|
|
|
