В одном из алгоритмов у нас возникают ключи, ключи это целые числа, каждый новый ключ должен быть уникален, поэтому для назначения нового ключа просто увеличивается глобальный счётчик на 1. В процессе работы некоторые ключи оказываются удалены, в итоге имеется множество целых чисел из диапазона [1, 32000] (например), которые реально присутствуют не все (например из них только 1000 чисел реально есть). Нужно перебрать все эти числа. Мы их все сложили в QSet<int> (хеш-множество), после чего перебор организовали одним из двух способов:
QSet<int> indices = ... ;
for (int i = 0; i < 32000; ++i)
{
if (indices.contains(i))
{
int corrent_index = i;
// some code
}
}
второй способ:
QSet<int> indices = ... ;
for (QSet<int>::iterator it = indices.begin(); it != indices.end(); ++it)
{
int corrent_index = *it;
// some code
}
Казалось бы, во второе варианте мы имеем в 20 раз меньший цикл. Однако замеры времени показывают, что второй цикл по времени более чем в 2 раза медленнее первого.
Это QSet<int> такой медленный? Или я что-то не так сделал?
Хотел попробовать std::unordered_set , но у нас отключена поддержка 11 стандарта, а быстро я её включить не смогу — там порядка 800 ошибок, связанных с constexpr ...
PS. Пытался убрать ненужные подробности, но если нужно — могу объяснить подробнее, что и зачем делается. Если очень общо — это часть реализации алгоритма выделения областей на бинарном изображении. Мы пытаемся его ускорить, оптимизацию отождествления индексов уже сделали (через disjoint set union, там дерево использовано, амортизированная сложность O(a(n)), что есть почти константа). Собственно это и есть индексы.
Здравствуйте, Кузнец, Вы писали:
К> for (QSet<int>::iterator it = indices.begin(); it != indices.end(); ++it)
А если QSet<int>::const_iterator? (см. справку: "Const iterators are slightly faster, and can improve code readability.")
Но это я так, пальцем в небо...
Здравствуйте, Anton Batenev, Вы писали:
AB>А если QSet<int>::const_iterator? (см. справку: "Const iterators are slightly faster, and can improve code readability.") AB>Но это я так, пальцем в небо...
Также сохраните результат вызова indices.end() перед циклом.
Можно еще попрофилировать второй вариант, чтобы понять что действительно тратит время.
К>QSet<int> indices = ... ;
К>for (QSet<int>::iterator it = indices.begin(); it != indices.end(); ++it)
К>{
К> int corrent_index = *it;
К> // some code
К>}
К>
К>Казалось бы, во второе варианте мы имеем в 20 раз меньший цикл. Однако замеры времени показывают, что второй цикл по времени более чем в 2 раза медленнее первого.
Это странно.
К>Это QSet<int> такой медленный? Или я что-то не так сделал?
Попробуйте так:
QSet<int> indices = ... ;
for (QSet<int>::iterator it = indices.begin(), itEnd = indices.end(); it != itEnd; ++it)
{
int corrent_index = *it;
// some code
}
[/ccode]
Да, std::set имеет логарифмическое время вставки, а unordered_set константу в среднем. Взамен std::set упорядочен, а другой порядок не гарантирует, в нашем же случае упорядоченность никак не помогает, но критично время обработки.
Здравствуйте, Кузнец, Вы писали:
R>>разные O-большие
К>Да, std::set имеет логарифмическое время вставки, а unordered_set константу в среднем. Взамен std::set упорядочен, а другой порядок не гарантирует, в нашем же случае упорядоченность никак не помогает, но критично время обработки.
это все понятно. но что-то мой опыт подсказывает мне, что все эти моменты на этом наборе данных с учетом что данные — интегралы — не имеют большого значения...
пачка бумаги А4 стОит 2000 р, в ней 500 листов. получается, лист обычной бумаги стОит дороже имперского рубля =)
Отвечаю в корень, так как это ответ на несколько постов.
Сделал const_iterator и запомнил indices.end() , чтобы не дёргать её в цикле (казалось бы, это должно было соптимизироваться, но ладно, запомнили вручную).
Всё равно время работы удивляет:
Один из отчётов по времени работы:
count = 5977 (max_index) 3322 (indices.size) — полный перебор почти 6000 интов, а хеш-множестве почти в 2 раза меньше
point1 dt= 2.2303e-05 — полный перебор циклом с проверкой наличия индекса в множестве
point2 dt= 5.9156e-05 — перебор константным итератором по хеш-множеству
Опять, перебор по множеству оказался почти в 2 раза медленнее. Конечно, уменьшение объёма в этот раз не существенное, но выходит, что итерирование по QSet'у как минимум в 4 раза медленнее итерации по целым числам.
При уменьшении перебора почти в 7 раз время работа выросло, ну хоть не в 2 раза, но всё равно существенно...
Это очень странно, либо хеш-множество реально много накладных расходов влечёт, либо я где-то очень неслабо накосячил... Проверить на косячность Qt'шную реализацию QSet'а не могу (в 11 стандарт нам нельзя, проект за 10 минут не поправлю, чтобы собрать с -std=c++11)... Можно попробовать сделать свою реализацию множества, но сомнительно, что свой велосипед обгонит библиотеку (если только у Qt нет какого-то косяка, всякое бывает).
Здравствуйте, niXman, Вы писали:
X>Здравствуйте, Кузнец, Вы писали:
R>>>разные O-большие
К>>Да, std::set имеет логарифмическое время вставки, а unordered_set константу в среднем. Взамен std::set упорядочен, а другой порядок не гарантирует, в нашем же случае упорядоченность никак не помогает, но критично время обработки.
X>это все понятно. но что-то мой опыт подсказывает мне, что все эти моменты на этом наборе данных с учетом что данные — интегралы — не имеют большого значения...
Эти данные не интегралы, это индексы. Наш алгоритм следует статье , каждому вновь найденному объекту присваивается индекс, иногда индексы приходится отождествить, при этом остаётся один из них (какой именно — определяет алгоритм отождествления, у нас там работает disjoint-set-union, поэтому нельзя сказать, например, что всегда выбирается меньший из двух). Эти индексы потом в QSet и были сложены, причём каждый клался столько раз, сколько других индексов было отождествлено, поэтому и пришлось испольховать хеш-множество, чтобы не заниматься каждый раз поиском по уже набранным индексам (можно было бы сложить в std::vector, но тогда мы бы имели много повторяющихся чисел, что сломает алгоритм)
Здравствуйте, Кузнец, Вы писали:
К>Отвечаю в корень, так как это ответ на несколько постов.
К>Сделал const_iterator и запомнил indices.end() , чтобы не дёргать её в цикле (казалось бы, это должно было соптимизироваться, но ладно, запомнили вручную).
К>Всё равно время работы удивляет:
Я надеюсь, что результаты приведены для релизной сборки.
Здравствуйте, solano, Вы писали:
S>Здравствуйте, Кузнец, Вы писали:
К>>Отвечаю в корень, так как это ответ на несколько постов.
К>>Сделал const_iterator и запомнил indices.end() , чтобы не дёргать её в цикле (казалось бы, это должно было соптимизироваться, но ладно, запомнили вручную).
К>>Всё равно время работы удивляет:
S>Я надеюсь, что результаты приведены для релизной сборки.
Разумеется. Релизная сборка, оптимизация -O3 . Попробую сейчас ещё с -O2 на всякий случай...
Здравствуйте, Кузнец, Вы писали: К>В одном из алгоритмов у нас возникают ключи, ключи это целые числа, каждый новый ключ должен быть уникален, поэтому для назначения нового ключа просто увеличивается глобальный счётчик на 1. В процессе работы некоторые ключи оказываются удалены, в итоге имеется множество целых чисел из диапазона [1, 32000] (например), которые реально присутствуют не все (например из них только 1000 чисел реально есть). Нужно перебрать все эти числа. Мы их все сложили в QSet<int> (хеш-множество), после чего перебор организовали одним из двух способов:
код
#include <QSet>
#include <QTime>
#include <QDebug>
void test (int count, int max = 32000)
{
QSet<int> set;
while (set.size() < count)
{
int x = qrand() % max;
set.insert(x);
}
const int repeat_count = 1000;
QTime t;
int c = 0;
t.start();
for (int n = 0; n < repeat_count; ++n)
{
for (int i = 0; i < max; ++i)
{
c += (int)set.contains(i);
}
}
qDebug() << "count1" << c / repeat_count << "time" << t.elapsed();
c = 0;
t.start();
for (int n = 0; n < repeat_count; ++n)
{
for (QSet<int>::const_iterator it = set.cbegin(), end = set.cend(); it != end; ++it)
{
++c;
}
}
qDebug() << "count2" << c / repeat_count << "time" << t.elapsed();
}
int main(int argc, char *argv[])
{
test(6000);
test(100);
return 0;
}
Qt 5.7 mingw 5.3
Результат
count1 6000 time 561
count2 6000 time 116
count1 100 time 329
count2 100 time 1
Здравствуйте, Кузнец, Вы писали:
К> Однако замеры времени показывают, что второй цикл по времени более чем в 2 раза медленнее первого. К> Это QSet<int> такой медленный? Или я что-то не так сделал?
Вообще говоря странно. Бенчмарк в студию.
Для такого размера чую простой bool[32000] может оказаться быстрее. Ещё std::bitset стоит попробовать.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, c-smile, Вы писали:
CS>Здравствуйте, Кузнец, Вы писали:
К>> QSet<int> (хеш-множество)
CS>hash table слабо подходит для итерирования.
CS>Для эффективного перебора hash table нужен либо поддержка им генераторов либо визиторов типа
CS>
CS>где перебор по существующим элементам может быть сделан максимально эффективно.
Сугубо не согласен. В текущем аспекте — и генераторы и визитор и итераторы — все они эквивалентны по стоимости, если их рассматривать как абстракции архитектурного подхода. На с++ можно все эти три абстракции реализовать с нулевой одинаковой стоимостью для себжевого случая — перебора элементов хэш-таблицы.
V>Сугубо не согласен. В текущем аспекте — и генераторы и визитор и итераторы — все они эквивалентны по стоимости, если их рассматривать как абстракции архитектурного подхода. На с++ можно все эти три абстракции реализовать с нулевой одинаковой стоимостью для себжевого случая — перебора элементов хэш-таблицы.
Ну не совсем так.
Когда в стандарт C++ добавляли хеш-таблицы (которые стали std::unordered_map и std::unordered_set), то даже в самом proposal было замечено, что классические итераторы C++ — плохие, и эффективно проитерироваться по хеш-таблице ими не получается: мешает их устаревший интерфейс. Под "эффективно" тут подразумевается по сравнению с другими способами итерирования по содержимому (один из которых — это метод for_each у контейнера).
Смотри, например, раздел "Bucket Interface" предложения по хеш-таблицам.
А о том, как можно исправить итераторы C++ (несовместимым образом, конечно же) можно прочитать в другом предложении: Segmented Iterators and Hierarchical Algorithms (лучше даже с него начать).
То есть классические итераторы в этом плане ущербны и действительно проигрывают по скорости другим альтернативам.
И хотя в bucket interface тоже есть нечто с названием local_iterator, но это совсем другой итератор. И обход хеш-таблицы через него записывается чуть хитрее чем просто for (auto it = indices.begin(); it != indices.end(); ++it).
Здравствуйте, c-smile, Вы писали:
К>> QSet<int> (хеш-множество) CS>hash table слабо подходит для итерирования.
Теоретически если количество бакетов не сильно больше, чем реальных элементов и мало коллизий, то итерироваться должно хорошо.
Но идея интересная — наверное у него размер set менялся в широких пределах и хеш-таблица стала раздутой, но полупустой. Поэтому итерирование и долгое.
В java я бы просто попробвал заменить на LinkedHashSet — он итерируется как обычный linked list.
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, watchmaker, Вы писали:
V>>Сугубо не согласен. В текущем аспекте — и генераторы и визитор и итераторы — все они эквивалентны по стоимости, если их рассматривать как абстракции архитектурного подхода. На с++ можно все эти три абстракции реализовать с нулевой одинаковой стоимостью для себжевого случая — перебора элементов хэш-таблицы.
W>Ну не совсем так. W>Когда в стандарт C++ добавляли хеш-таблицы (которые стали std::unordered_map и std::unordered_set), то даже в самом proposal было замечено, что классические итераторы C++ — плохие, и эффективно проитерироваться по хеш-таблице ими не получается: мешает их устаревший интерфейс. Под "эффективно" тут подразумевается по сравнению с другими способами итерирования по содержимому (один из которых — это метод for_each у контейнера). W>Смотри, например, раздел "Bucket Interface" предложения по хеш-таблицам. W>А о том, как можно исправить итераторы C++ (несовместимым образом, конечно же) можно прочитать в другом предложении: Segmented Iterators and Hierarchical Algorithms (лучше даже с него начать).
Они имели ввиду несколько иное. Они предложили не то чтобы "тотальный подход, использовать всем!", а лишь "оптимизацию для некоторых специфических наполнений хэш-таблицы", при которых количество элементов в букете будет велико (то есть, наполнения при большом количестве коллизий между ключами). На практике такие наполнения встречаются редко. Обычно народ вполне грамотно подбирает хэш-функцию, обеспечивая минимум или даже полное отсутствие коллизий. За счет этого контейнер способен очень эффективно размазывать ключи по букетам. Таким образом, основная наполненность отдельно-взятого букета составляет 1 или ноль элементов, и лишь иногда (при коллизиях хэшфункции или коллизии размазывателя) получаются букеты с более чем одним элементом.
Насчет бумаги Segmented Iterators and Hierarchical Algorithms — обрати внимание, она опирается на ЭВМ 20-летней давности (упоминается 150 MHz MIPS R5000). Сегодняшние ЭВМ существенно отличаются по своим характеристикам, в частности, у них другая расфасовка стоимостей различных команд, за счет другой архитектуры (в основном из за кэширования ОЗУ и предсказание переходов). Я к тому, что заявленные в бумаге тайминги — они на современном железе будут несколько другие.
W>То есть классические итераторы в этом плане ущербны и действительно проигрывают по скорости другим альтернативам.
Да нет же
Никакой ущербности нет. Некоторая специфика есть, да. Например, если хэш таблица будет с большим количеством коллизий — то букетный перебор за счет этой особенности может выиграть. Но давай не будем рассматривать аномальные случаи.
С алгоритмической стороны, применение итераторов, генераторов, переборщика each_value, а теперь еще и упомянутый итераторБукета+итераторВнутриБукета — эквивалентны по затратам, так как имеют равные составы низкоуровневых инструкций в своей алгоритмике. Можно построить реализации любого из этих трех подходов и они будут одинаково быстро работать. Ну, конечно, с точностью до погрешности замеров, способностей оптимизатора кодогенерации и особенностей исполняющей машины.
Попробуй сам замерить, классические итераторы vs букет-итераторы, будешь удивлен.
[добавка]
Вычитал мотивировку G. Bucket Interface из пропозала... Они там ничего не говорят об ущербности итераторов для перебора элементов. Основное обоснование Bucket Interface — чтобы можно было контролировать распределение элементов по букетам (то есть, качество хэш-функции и подобные моменты, специфические для хэш-таблицы). О скоростях перебора — лишь только следующий кусок
if the iterators have an underlying segmented structure (as they do in existing singly linked list implementations), algorithms that exploit that structure, with an explicit nested loop, can be more efficient than algorithms that view the elements as a flat range
То есть, если некий пользовательский алгоритм переработки элементов будет способен эффективно использовать именно букетность представления данных вместо линейности — то он сможет это сделать. Обрати внимание, для получения бОльшей эффективности — у алгоритма переработки должна быть 'особенность' (an explicit nested loop), которая при сопряжении с букетным представлением может дать профит. Нет особенности — нет профита.
