Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > sort и uniq для вектора очень большого размера

Автор: rudolfninja 4.2.2016, 22:23

Ребята, приветствую.

Ситуация:
есть файл, в котором содержится очень много строк (от 250 000 до 300 000). Длина строки фиксированная - 30 байтов. Мне надо эти строки обрабатывать. Строки могут повторятся, поэтому сначала я оставляю только уникальные строки.
Алгоритм такой:
1) Читаю из файла все строки в вектор:

Код


if (data.is_open())
    {
        while (!data.eof())
        {
            string str;
            data >> str;
            if (!str.empty())
                src_vec.push_back(str);
        }
        data.close();
    }

2) Сортирую вектор:

Код


sort(src_vec.begin(), src_vec.end());

3) Удаляю дубликаты строк:

Код


src_vec.resize(unique(src_vec.begin(), src_vec.end()) - src_vec.begin());

Проблема в том, что с таким количеством строк программа валится на моменте сортировки.
Вопрос вот в чем, подскажите, как можно правильно и корректно поступить в данной ситуации?
Спасибо.

P.S. В названии темы неправильно написано слово "unique". Прошу прощения. smile

Автор: Amp 4.2.2016, 23:17

Если валится, то кэлстэк было бы неплохо приложить. Вектор у тебя из std::string? Компаратор какой-нибудь свой в std::sort передаешь?

Автор: rudolfninja 5.2.2016, 00:21

Вектор из std::string, своего компаратора никакого не писал.
Блин, сейчас на компе была запущена только студия и все нормально отработало. Буду пробовать еще раз словить падение и скину колстек.

Автор: leniviy 5.2.2016, 12:14

Если нужен sort+uniq, то сначала сортировать, а потом выбирать uniq - плохая идея. Лучше сразу вместо вектора использовать сет.

Раз длина строк фиксированная, значит std::string не нужен. Экономнее читать каждую строку в массив байтов.

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com/sort-i-uniq-dlya-vektora-ochen-bolshogo-razmera-id56b3a553ae20158b368b4567#findElement_E7045_56b467ddae2015fa2df1a28a_0

Автор: Sajtran 5.2.2016, 14:31

Цитата

Проблема в том, что с таким количеством строк программа валится на моменте сортировки.

стэк для программы увеличь, QSort иногда много его жрёт или не стековую сортировку какую ни будь используй

Этот ответ добавлен с нового Винграда - http://ru.vingrad.com/sort-i-uniq-dlya-vektora-ochen-bolshogo-razmera-id56b3a553ae20158b368b4567#findElement_E7045_56b4881bae20155455f1a025_0

Автор: rudolfninja 5.2.2016, 19:44

Ребят, с сортировкой разобрался. Оказывается, в программе, которая генерирует данные есть возможность писать их в файл уже отсортированными =)
Всем спасибо за ответы.
Дальше слегка не по теме...
Возник такой вопрос: очень медленно отрабатывает функция erase для вектора. Есть такой код:

Код


input curr_data, next_data;
for (int i = 0; i < input_vec.size() - 2; i++)
{
    curr_data = input_vec[i];
    next_data = input_vec[i + 1];

    if ((curr_data.chanel == next_data.chanel) && (curr_data.owner == next_data.owner) && (curr_data.wathcers == next_data.wathcers))
    {
        input_vec.erase(input_vec.begin() + (i + 1));
        i--;
    }
}

Получается, что бывают моменты, что счетчик декрементируется, тем самым увеличивая время выполнения цикла. Этот цикл отрабатывает оооочень долго smile

. Даже когда под отладчиком пошагово прохожу, то длительное время зависаю на функции erase. В теории, насколько я понимаю, после каждого удаления процесс удаления становится быстрее, т.к. количество элементов в векторе уменьшается (хотя, я не уверен в этом, т.к. не знаю как реализовано удаление в векторе), но все равно, процесс очень долгий.
Есть варианты, как ускорить все это дело? Может использовать не вектор, а что-либо еще? Просто с моим количеством записей в этом векторе (около 250тыс) удаление занимает довольно длительное время...я бы даже сказал, что выполнение этого цикла сильно тормозит работу программы.
Подскажите, пожалуйста, как ускорить сие действо?
P.S. Элементы вектора отсортированы и важно сохранить это.

Автор: volatile 5.2.2016, 21:30

Цитата(rudolfninja @ 5.2.2016, 19:44

)

в программе, которая генерирует данные есть возможность писать их в файл уже отсортированными

Если вы читаете из файла уже отсортированные, то просто изначально не добавляйте дубликаты.
(проверяйте при чтении)

Автор: xvr 8.2.2016, 12:54

Цитата(rudolfninja @ 5.2.2016, 19:44

)

очень медленно отрабатывает функция erase для вектора

Это ожидаемо. vector хранит элементы в линейном масиве памяти. erase приводит к перезаписи половины элементов (в среднем)

Цитата(rudolfninja @ 5.2.2016, 19:44

)

Может использовать не вектор, а что-либо еще?

Угу, лучше всего list. И еще лучше дать ему свой allocate, что бы элементы располагались в общем пуле памяти, а не насиловали общую кучу С++ smile

Цитата(volatile @ 5.2.2016, 21:30

)

Если вы читаете из файла уже отсортированные, то просто изначально не добавляйте дубликаты.

А это еще лучше smile

Автор: rudolfninja 8.2.2016, 13:40

В общем да, порешал проблему...чуток изменил алогритм и все летает.
Всем спасибо.