crossplatform.ru

Здравствуйте, гость ( Вход | Регистрация )

7 страниц V  < 1 2 3 4 5 > »   
Ответить в данную темуНачать новую тему
> Бысрый способ получить 100 наименьших элементов, из 10 000 000 000 записей или более
igor_bogomolov
  опции профиля:
сообщение 21.8.2010, 23:10
Сообщение #21


Профессионал
*****

Группа: Сомодератор
Сообщений: 1215
Регистрация: 22.3.2009
Из: Саратов
Пользователь №: 630

Спасибо сказали: 235 раз(а)




Репутация:   29  


Цитата(DEADHUNT @ 22.8.2010, 0:00) *
а смысл называть это списком, если по сути это вектор? список оптимизирован под вставку - а здесь O(n).
Я не знаю ответа на этот вопрос. Почему то разработчики Qt поступили именно так, и, при небольших количествах элементов, QList - это вектор
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 9:32
Сообщение #22


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


А вот мое решение.
    std::vector <int> etalon;

    for (int i = 10000000; i > 0; i--) {
        etalon.push_back (i);
    }

    std::vector <int> v (100);
    copy (etalon.begin (), etalon.begin () + 100, v.begin ());
    sort (v.begin (), v.end ());

    for (std::vector <int>::const_iterator eIt = etalon.begin () + 100, eEnd = etalon.end (); eIt != eEnd; ++eIt) {
        if (*eIt < *v.begin ()) {
            continue;
        }

        std::vector <int>::iterator it = find (v.begin () + 1, v.end (), *eIt);
        v.insert (it, *eIt);
        v.erase (v.begin ());
    }

Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
Алексей1153
  опции профиля:
сообщение 24.8.2010, 10:03
Сообщение #23


фрилансер
******

Группа: Участник
Сообщений: 2890
Регистрация: 19.6.2010
Из: Обливион
Пользователь №: 1822

Спасибо сказали: 215 раз(а)




Репутация:   34  


тут одно только заполнение вектора etalon (зачем-то) всё время покроет )

Сообщение отредактировал Алексей1153 - 24.8.2010, 10:04
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 10:10
Сообщение #24


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


Это только для проверки. Он и является нужным контейнером.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 24.8.2010, 10:21
Сообщение #25


Мастер
******

Группа: Модератор
Сообщений: 3291
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


panter_dsd, в твоем случае не оптимально по скорости.
При добавлении нового элемента вектора, вектор расширяется, выделяется память для его нового элемента и копируются все элементы вектора в новый участок памяти. (вспомни, почему нельзя пользоваться полученными итераторами на элемент вектора, после добавления нового элемента, пускай даже в конец вектора).
При удалении первого элемента вектора "v" что происходит со всем вектором? Вроде как все элементы вектора сдвигаются. Насчет перераспределения памяти не помню, что происходит.
А так как ты для примера выбрал самый не трудоемкий случай, то это в принципе очень не критично, но если поменять цикл заполнения etalon от 0 до ... то это будет происходить в каждой итерации цикла.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
kwisp
  опции профиля:
сообщение 24.8.2010, 10:23
Сообщение #26


астарожна ынтжинэр
*****

Группа: Участник
Сообщений: 1404
Регистрация: 26.11.2008
Из: ТаганрогРодинаЧехова
Пользователь №: 435

Спасибо сказали: 113 раз(а)




Репутация:   23  


panter_dsd,
он имеет ввиду что вектор заполнить можно значительно быстрее чем делаешь ты.
при каждом твоем push_back происходит выделение памяти. хотя память под элементы можно выделить одним махом при создании вектора.
ну тут долгая песня
Скот Меерс в руки и вперед.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 10:27
Сообщение #27


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


Согласен. Вставку не учел. На счет удаления знал, но решил пренебречь. заменяем вектор на лист и избавляемся от этого.

Блин, создание эталонного массива просто для примера. Не смотрите туда.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
ViGOur
  опции профиля:
сообщение 24.8.2010, 10:35
Сообщение #28


Мастер
******

Группа: Модератор
Сообщений: 3291
Регистрация: 9.10.2007
Из: Москва
Пользователь №: 4

Спасибо сказали: 231 раз(а)




Репутация:   40  


Цитата(panter_dsd @ 24.8.2010, 11:27) *
Блин, создание эталонного массива просто для примера. Не смотрите туда.
Я на эталон как раз потому и не смотрел.
Обновленный код тогда в студию... :)

p.s. эталон разумеется оставь, он для наглядности, только поменяй его заполнение на более сложный случай, когда последующее число больше предыдущего.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 10:38
Сообщение #29


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


Я сейчас с телефона , позже выложу код.
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение
panter_dsd
  опции профиля:
сообщение 24.8.2010, 13:44
Сообщение #30


Жаждущий знаний
***

Группа: Участник
Сообщений: 254
Регистрация: 1.1.2009
Из: Санкт-Петербург
Пользователь №: 474

Спасибо сказали: 32 раз(а)




Репутация:   3  


#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

int main (int argc, char **argv) {
    //This is only for test!!!
    std::vector <int> etalon;
    etalon.reserve (10000000);

    for (int i = 0; i < 10000000; i++) {
        etalon.push_back (i);
    }

    std::cout << "Start" << std::endl;
    //Start
    std::list <int> l (etalon.begin (), etalon.begin () + 100);
    l.sort ();
    
    for (std::vector <int>::const_iterator eIt = etalon.begin () + 100, eEnd = etalon.end (); eIt != eEnd; ++eIt) {
        if (*eIt < *l.begin ()) {
            continue;
        }

        std::list <int>::iterator it = lower_bound (l.begin (), l.end (), *eIt);
        l.insert (it, *eIt);
        l.pop_front ();
    }

    for (std::list <int>::iterator it = l.begin (), end = l.end (); it != end; ++it) {
        std::cout << *it << std::endl;
    }

    return 0;
}

Вот измененный код. Коррективы приветствуются.
Можно функцию в виде темплейта оформить, но пока не знаю как, еще не дошел до этого. :)
Только заметил, что ищу 100 максимальных значений, лопухнулся. Ну, принцип тот же самый.

Сообщение отредактировал panter_dsd - 24.8.2010, 16:48
Перейти в начало страницы
 
Быстрая цитата+Цитировать сообщение

7 страниц V  < 1 2 3 4 5 > » 
Ответить в данную темуНачать новую тему
Теги
Нет тегов для показа


1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0




RSS Текстовая версия Сейчас: 15.12.2019, 0:34