Организация произвольного построчного чтения

[Spark]

Создаю слайдшоу. Имена карточек берутся из списка по порядку, построчно - http://www.prog.org.ru/topic_25276_15.html

Необходимо организовать режим Random (случайное чтение), учитывая, что список может быть большим (тысяч сто). Т.е список надо перемешать и затем выдавать по порядку (что бы не было повторов).
Подскажите как это организовать?
Рад любой помощи.

[kambala]

1) быстрый способ: засунуть строки в хэш или множество и извлекать оттуда, получится такой себе не очень рандомный рандом
2) нормальный способ: генерировать случайный индекс через qrand(), извлекать по нему строку, помещать индекс во множество для проверки уникальности

[Igors]

2) нормальный способ: генерировать случайный индекс через qrand(), извлекать по нему строку, помещать индекс во множество для проверки уникальности

Проще перемешать сами элементы контейнера напр

Код

C++ (Qt)
QStringList lst;
...
for (int i = 0; i < lst.size(); ++i)
 lst.swap(qrand() % lst.size(), qrand() % lst.size()); 
 

А потом брать подряд

[m_ax]

Код

C++ (Qt)
QStringList list;
...
std::random_shuffle(list.begin(), list.end());
 

[kambala]

да уж, надо изучить STL получше

[Igors]

Код

C++ (Qt)
QStringList list;
...
std::random_shuffle(list.begin(), list.end());
 

Это заметно хуже предыдущего варианта (см описание QList::swap)

[m_ax]

Код

C++ (Qt)
QStringList list;
...
std::random_shuffle(list.begin(), list.end());
 

Это заметно хуже предыдущего варианта (см описание QList::swap)

Это Ваше очередное заблуждение..

Давайте посмотрим на тесты:

Код

C++ (Qt)
#include <iostream>
#include <list>
#include <algorithm>
#include <QStringList>
#include <ctime>
#include <chrono>
 
template <unsigned N>
void initList(QStringList & list) {
    for (unsigned i = 0; i < N; ++i) {
        list << QString::number(i);
    }
}
 
int main()
{
 
    using namespace std::chrono;
    const unsigned Num = 1000000;
 
    QStringList list;
 
    initList<Num>(list);
 
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    std::random_shuffle(list.begin(), list.end());
    high_resolution_clock::time_point t2 = high_resolution_clock::now();
 
    duration<double> time_span = duration_cast<duration<double>>(t2 - t1);
    std::cout << "random_shuffle: " << time_span.count() << " seconds." << std::endl;
 
    t1 = high_resolution_clock::now();
    for (int i = 0; i < list.size(); ++i) {
        list.swap(qrand() % list.size(), qrand() % list.size());
    }
    t2 = high_resolution_clock::now();
 
    time_span = duration_cast<duration<double>>(t2 - t1);
    std::cout << "igors: " << time_span.count() << " seconds." << std::endl;
 
 
    return 0;
}
 

Результаты у меня такие (3 испытания)

Код

Bash
random_shuffle: 0.172468 seconds.
igors: 0.403365 seconds.
 
random_shuffle: 0.1679 seconds.
igors: 0.350107 seconds.
 
random_shuffle: 0.162135 seconds.
igors: 0.362432 seconds.
 

Результаты ясно говорят, что random_shuffle эффективнее более чем в два раза..

[Old]

Результаты ясно говорят, что random_shuffle эффективнее более чем в два раза..

А время на изучение почему ваш тест не выводит, так сказать на поиск и рыскатню?

[m_ax]

Результаты ясно говорят, что random_shuffle эффективнее более чем в два раза..

А время на изучение почему ваш тест не выводит, так сказать на поиск и рыскатню?

 
Моё лицо упало на пол, потом я долго долго плакал)

[Igors]

Результаты ясно говорят, что random_shuffle эффективнее более чем в два раза..

У меня др результаты (gcc/icc практически одинаковы)

random_shuffle: 298 ms.
igors: 126 ms.

Немного изменил Ваш пример т.к. не имею С++ 11. На всякий случай вот полный текст

Код

C++ (Qt)
#include <iostream>
#include <algorithm>
#include <QtGUI>
 
template <unsigned N>
void initList(QStringList & list) {
    for (unsigned i = 0; i < N; ++i) {
        list << QString::number(i);
    }
}
 
int main()
{
    const unsigned Num = 1000000;
    QStringList list;
    initList<Num>(list);
 
    QTime t1 = QTime::currentTime();
    std::random_shuffle(list.begin(), list.end());
    std::cout << "random_shuffle: " << t1.elapsed() << " ms." << std::endl;
 
    t1 = QTime::currentTime();
    for (int i = 0; i < list.size(); ++i) 
	list.swap(i, qrand() % list.size());
    std::cout << "igors: " << t1.elapsed() << " ms." << std::endl;
 
    return 0;
}
 

Перемещать данные не есть хорошо/грамотно - нужно перемещать указатели. И здесь еще так-сяк с имплисит шарой

[m_ax]

С Вашим модифицированным вариантом результаты у меня:

Код

Bash
random_shuffle: 163 ms.
igors: 229 ms.
 
random_shuffle: 159 ms.
igors: 229 ms.
 
random_shuffle: 192 ms.
igors: 233 ms.
 

gcc 4.6.3

Architecture:               x86_64
CPU(s):                      1
On-line CPU(s) list:     0
Thread(s) per core:      1
Vendor ID:                  AuthenticAMD
CPU MHz:                  1808.327

[Igors]

С Вашим модифицированным вариантом результаты у меня:

Не знаю. Я уже и тесты поменял местами, добавил srand и qsrand - все то же самое gcc/icc 32/64. debug/release. Вот последний вариант (хотя принципиальной разницы никакой)

Код

C++ (Qt)
#include <iostream>
#include <algorithm>
#include <QtGUI>
 
template <unsigned N>
void initList(QStringList & list) {
    for (unsigned i = 0; i < N; ++i) {
        list << QString::number(i);
    }
}
 
int main()
{
    const unsigned Num = 1000000;
    QStringList list;
    initList<Num>(list);
    qsrand(0); 
 
    QTime t2 = QTime::currentTime();
    for (int i = 0; i < list.size(); ++i) 
	list.swap(i, qrand() % list.size());
    std::cout << "igors: " << t2.elapsed() << " ms." << std::endl;
 
    srand(0);
    QTime t1 = QTime::currentTime();
    std::random_shuffle(list.begin(), list.end());
    std::cout << "random_shuffle: " << t1.elapsed() << " ms." << std::endl;
 
    return 0;
}
 

[Old]

А версии и разработчики stl думаю отличаются существенно. У вас даже стандарты разные.

[Old]

Проверил у себя, последний тест:

Код:

igors: 83 ms.
random_shuffle: 59 ms.

g++ (GCC) 4.8.1

Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
Thread(s) per core:    1
Core(s) per socket:    4
Socket(s):             1
NUMA node(s):          1
Vendor ID:             AuthenticAMD
CPU family:            16
Model:                 4
Model name:            AMD Phenom(tm) II X4 945 Processor
Stepping:              2
CPU MHz:               800.000
BogoMIPS:              6030.87
Virtualization:        AMD-V
L1d cache:             64K
L1i cache:             64K
L2 cache:              512K
L3 cache:              6144K
NUMA node0 CPU(s):     0-3

[Spark]

Спасибо за помощь.
Понял пока только  в каком направлении двигаться, остальное не понял . Но наверное на изучение вопроса придется потратить ночь.
Из того, что понял.
- Надо создать:

Код

C++ (Qt)
QStringList lst;

- Далее каким то образом перетащить в него все пункты с текстового файла.
- Затем перемешать:

Код

C++ (Qt)
for (int i = 0; i < lst.size(); ++i)
 lst.swap(qrand() % lst.size(), qrand() % lst.size());

В списке (колонке) 100.000 пунктов. Тормозить не будет?