Задача получить 100 наименьших элементов из массива в 10 000 000 000 записей, записи это числа.
Как это сделать, побыстрей?
А массив где находится? Отсортирован ли? Каков размер элементов?
пока свернул, чтобы
ViGOur, я так понимаю это одно из заданий с собеседования?
Если не секрет, какие мысли были у тебя?
Вот задача. Очевидный шаг это отсортировать массив и взять первые 100 значений.
Посидел, подумал, набросал тестовый примерчик и оказалось, что даже без оптимизации кода, можно написать алгоритм который это делает значительно быстрее (на время не тестил и так все видно).
Использовал контейнеры Qt. Функция состоит из 13 строк.
Код пока приводить не буду, интересны идеи других форумчан.
вот
<удалил это безобразие>
Алексей1153, что за метод такой resize у map?
Ну вот, вы сразу map и прочее, с map это халява.
Представьте, что нет никакого STL. Есть чистый С\С++ и все!
Да на собеседовании задали, я ответил неправильно, только потом додумался как это можно сделать.
typedef quint32 Number;
typedef QVector<Number> VecNumber;
typedef QList<Number> LstResult;
const int sizeDataVector = 10000000;
const int sizeResultList = 100;
LstResult find100min( const VecNumber &vec )
{
Number maxValue = -1;
LstResult result;
// Заполняем список результатов максимально возможными значениями
for( int i = 0; i < sizeResultList; ++i )
result.append( -1 );
foreach( Number val, vec )
{
// Если текущее значение больше самого большого значения в результатах, то прорускаем его
if( val > maxValue )
continue;
// иначе, вставляем его в результаты
result.insert( qLowerBound( result.begin(), result.end(), val ), val );
// отбрасываем последнее значение
result.removeLast();
// устанавливаем maxValue равное последнему элементу результата
maxValue = result.last();
}
return result;
}
мда, с мапом затея не очень оказалась - итератор на наибольший элемент хрен так сразу получишь ) А искать его каждый раз - будет накладно
А ещё, креатор отказался понимать итераторы , поэтому пробовал в студии
template<typename T>
void F()
{
std::map<T,int>::iterator it;
}
template<typename T>
void F()
{
typename std::map<T,int>::iterator it;
}
std::vector<int> min_elements(100, values[0]);
for (std::list<int>::const_iterator it = values.begin();
it != values.end(); ++it)
{
if (min_elements.back() > *it)
{
min_elements.back() = *it;
std::sort(min_elements.begin(), min_elements.end());
}
}
DEADHUNT, наверное, правильНЕЕ , но студия понимает и так
Кстати, победил:
template<typename T>
void find_most_little_elenents(std::vector<T>& vResut,const T* beg,const T* end,const unsigned int countToFind)
{
struct Tr
{
T t;
Tr(T& t):t(t){}
bool operator<(const Tr& o2)const{return t>o2.t;}
};
vResut.clear();
typedef std::multimap<Tr,int> td_mapOut;
td_mapOut mapOut;
for(T* t=(T*)beg;t<end;t++)
{
if(mapOut.size()==countToFind && mapOut.begin()->first.t <= *t)
{
}
else
{
mapOut.insert(td_mapOut::value_type(*t,0));
if(mapOut.size()>countToFind)
{
mapOut.erase(mapOut.begin());
}
}
}
unsigned int dwd=0;
vResut.resize(mapOut.size());
for(
td_mapOut::reverse_iterator it=mapOut.rbegin();
it!=mapOut.rend();
it++,dwd++
)
{
vResut[dwd]=it->first.t;
}
}
Алексей1153, как то у тебя нагромаждённо получается, наверняка можно было проще твой вариант сделать.
igor_bogomolov, а вот пример использования, который креатор тоже не прожевал, а студия понимает нормально. Тут то что не так ))
char c[]="183743652425643758462";
std::vector<char> vec;
find_most_little_elenents(vec,c,c+sizeof(c)-1,5);//<<ругается сюда
std::vector<int> min_elements(100, values[0]);
for (std::list<int>::const_iterator it = values.begin();
it != values.end(); ++it)
{
if (min_elements.back() > *it)
{
std::vector<int>::iterator pos = std::lower_bound(min_elements.begin(), min_elements.end(), *it);
*pos = *it;
}
}
А вот мое решение.
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 ());
}
тут одно только заполнение вектора etalon (зачем-то) всё время покроет )
Это только для проверки. Он и является нужным контейнером.
panter_dsd, в твоем случае не оптимально по скорости.
При добавлении нового элемента вектора, вектор расширяется, выделяется память для его нового элемента и копируются все элементы вектора в новый участок памяти. (вспомни, почему нельзя пользоваться полученными итераторами на элемент вектора, после добавления нового элемента, пускай даже в конец вектора).
При удалении первого элемента вектора "v" что происходит со всем вектором? Вроде как все элементы вектора сдвигаются. Насчет перераспределения памяти не помню, что происходит.
А так как ты для примера выбрал самый не трудоемкий случай, то это в принципе очень не критично, но если поменять цикл заполнения etalon от 0 до ... то это будет происходить в каждой итерации цикла.
panter_dsd,
он имеет ввиду что вектор заполнить можно значительно быстрее чем делаешь ты.
при каждом твоем push_back происходит выделение памяти. хотя память под элементы можно выделить одним махом при создании вектора.
ну тут долгая песня
Скот Меерс в руки и вперед.
Согласен. Вставку не учел. На счет удаления знал, но решил пренебречь. заменяем вектор на лист и избавляемся от этого.
Блин, создание эталонного массива просто для примера. Не смотрите туда.
Я сейчас с телефона , позже выложу код.
#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;
}
Готово. Сделал для любого кол-ва элементов. Хотелось бы еще для любого типа.
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
std::list <int> getNLager (const std::vector <int> &v, int n);
int main (int argc, char **argv) {
std::vector <int> etalon;
etalon.reserve (1000000);
for (int i = 0; i < 1000000; i++) {
etalon.push_back (i);
}
std::list <int> l = getNLager (etalon, 100);
for (std::list <int>::iterator it = l.begin (), end = l.end (); it != end; ++it) {
std::cout << *it << std::endl;
}
return 0;
}
std::list <int> getNLager (const std::vector <int> &v, int n)
{
if (n >= v.size ()) {
return std::list <int> ();
}
std::list <int> l (v.begin (), v.begin () + n);
l.sort ();
for (std::vector <int>::const_iterator eIt = v.begin () + n, eEnd = v.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 ();
}
return l;
}
1)
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
template<typename T>
void getNLager (typename const std::vector <T> &v, unsigned int n,std::list<T>& list_out)
{
typedef std::list<T> td_LIST;
list_out.clear();
if(!v.size ())return;
if (n >= v.size ()) return;
list_out.insert (list_out.begin() ,v.begin (), v.begin () + n);
list_out.sort ();
for (typename std::vector<T>::const_iterator eIt = v.begin() + n; eIt != v.end(); ++eIt)
{
if (*eIt < *list_out.begin ())
{
continue;
}
typename td_LIST::iterator it = lower_bound (list_out.begin (), list_out.end (), *eIt);
list_out.insert (it, *eIt);
list_out.pop_front ();
}
}
int main (int argc, char **argv)
{
std::vector <int> etalon;
etalon.reserve (1000000);
for (int i = 0; i < 1000000; i++)
{
etalon.push_back (i);
}
std::list <int> l;
getNLager (etalon, 100, l);
for (std::list <int>::iterator it = l.begin (); it!=l.end (); ++it)
{
std::cout << *it << std::endl;
}
return 0;
}
1. Учту.
2. Согласен.
4. Учту.
5. Не согласен. Можно и нужно, если контейнер не изменяется. Зачем дергать функцию на каждой итерации?
6. Вполне получается. Что смущает?
5 - в релизе там не будет функции Так что, дёргай без опаски
6 - ну, раз получается, тогда пользуйся на здоровье. У меня компилятор брыкается )) Ну оно и понятно
6. Компилятор ничего не говорит. По документации тоже можно, вроде бы. Завтра перепроверю.
всё, 6 - мой косяк )) Исправил . Пропустил начальный итератор и не обратил внимание
list_out.insert (list_out.begin() ,v.begin (), v.begin () + n);
kwisp, ок, учтём ) Только обычно у меня такой вызов был не в цикле, а list ещё не доводилось пользоваться почему то ))
Алексей1153, что-то не компилируется твой код.
g++ ./main.cpp
./main.cpp:7: ошибка: переменная или поле ‘getNLager’ объявлено void
./main.cpp:7: ошибка: expected nested-name-specifier before ‘const’
./main.cpp:7: ошибка: expected ‘(’ before ‘const’
./main.cpp:7: ошибка: expected primary-expression before ‘unsigned’
./main.cpp:7: ошибка: expected primary-expression before ‘&’ token
./main.cpp:7: ошибка: нет декларации ‘outList’ в этой области видимости
./main.cpp: In function ‘int main(int, char**)’:
./main.cpp:48: ошибка: нет декларации ‘getNLager’ в этой области видимости
panter_dsd, я в студии делал - там компилится. А ты где?
А ты, случаем, не поставил main перед реализацией функции ? )
тогда предопределение попробуй добавить перед мейном:
template<typename T>
void getNLager (typename const std::vector <T> &v, unsigned int n,std::list<T>& list_out);
Выкидывание typename помогло.
Алексей1153, что-то мне интересно. С шаблонами хорошо знаком, а компилятор от IDE и библиотеки отделить не можешь...
Я компилировал g++ (Gentoo 4.4.4-r1 p1.1, pie-0.4.5) 4.4.4. Т.е. не студийным компилером.
Заканчиваем с оффтопом.
Вот последняя редакция, еще есть замечания?
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
template<typename T>
void getNLager (const std::vector <T> &v, std::vector<T>& vOut, uint n)
{
vOut.clear();
if (v.empty () || n >= v.size ()) {
return;
}
std::list <T> l;
l.insert (l.begin() ,v.begin (), v.begin () + n);
l.sort ();
for (typename std::vector<T>::const_iterator eIt = v.begin() + n, eEnd = v.end (); eIt != eEnd; ++eIt) {
if (*eIt < *l.begin ()) {
continue;
}
const typename std::list <T>::iterator it = lower_bound (l.begin (), l.end (), *eIt);
l.insert (it, *eIt);
l.pop_front ();
}
vOut.reserve (n);
vOut.assign (l.begin (), l.end ());
}
int main (int argc, char **argv)
{
std::vector <int> etalon;
etalon.reserve (1000000);
for (int i = 0; i < 1000000; i++) {
etalon.push_back (i);
}
std::vector <int> v;
getNLager (etalon, v, 100);
for (std::vector <int>::iterator it = v.begin (), end = v.end (); it!=end; ++it) {
std::cout << *it << std::endl;
}
return 0;
}
Перенес флейм в другую тему, В любимый Алексей1153 раздел "Треп", чтобы потрепаться.
Смотрите: http://www.forum.crossplatform.ru/index.php?showtopic=5486.
Эдик, я вот одного не понял. Ты поставил условие - без использования стандартных контейнеров и прочего, а тут решения лишь с ними и приводят! Почему?
nth_element() - не катит?
std::vector<int> values; // 100000000 чисел
std::nth_element(values.begin(), values.begin() + 100, values.end()); // первые 100 чисел в values - минимальные
Как и обещал, код:
#include <algorithm>
#include <vector>
void fillValue( int &rValue)
{
static int n = 0;
n++;
rValue = n;
}
int main()
{
const size_t N = 10000;
const size_t M = 10;
std::vector<int> coll( N);
std::for_each( coll.begin(), coll.end(), fillValue); // заполняем
std::random_shuffle( coll.begin(), coll.end()); // рандомизируем, чтобы числа были не по порядку
std::vector<int> collMin( M, 0);
size_t collSize = coll.size();
size_t collMinSize = collMin.size();
// Здесь мы делали подготовительную работу по наполнению и эмуляции массивов, далее будет основная...
for( size_t n = 0; n < collSize; ++n)
{
if( n >= collMinSize)
{
int nMaxNumPos = 0;
for( size_t x = 0; x < collMinSize; ++x)
{
if( collMin[x] > collMin[nMaxNumPos])
nMaxNumPos = x;
}
if( collMin[nMaxNumPos] > coll[n])
collMin[nMaxNumPos] = coll[n];
}
else
{
collMin[n] = coll[n];
}
}
return 0;
}
1. rValue = ++n; - зачем в 2 строки делать?
2. std::vector<int> collMin( coll.begin(), coll.begin() + n); все же лучше.
1. Кому как нравится.
2. Чем лучше?
1. Если хочется в 2 строки, то хотя бы префиксную версию инкремента юзай.
2. Избавляемся от лишнего заполнения нулями, плюс от else, который только путает.
1. в данном случае точно разницы нет постфиксный инкремент или префиксный!
2. То, что избавляет от лишнего заполнения нолями, согласен. Но ИМХО мой вариант наглядней будет.
Всё равно, можно сказать, что ты выиграл M процессорных тактов на заполнении нолями и столько же можно убрать из цикла!
Но с другой стороны, это ведь подготовительная часть, и она нужна, чтобы не реализовывать ручками выделение памяти и её заполнение.
Тоесть только для наглядности!
Объясни как. Можно использовать только два массива!
Форум Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)