Динамический прямоугольный массив в Си++

Ок, спасибо=) Не понял просто.

На самом деле я только что понял, что он имел в виду! Он решил шуткануть как ъ-математик, а когда увидел, что его восприняли всерьез не попытался сказать, что это шутка была, а отправил в гугл и придрался к образованию. Зря потраченное время...

Если я правильно осилил ваши кулл-мапы и ваши кресты:

//map
map.size() = 0 ->insert = 10133697ips find = 18352241ips 
map.size() = 1024 ->insert = 10390506ips find = 16517727ips 
map.size() = 2048 ->insert = 9683031ips find = 14241260ips 
map.size() = 4096 ->insert = 8548480ips find = 11689647ips 
map.size() = 8192 ->insert = 7416413ips find = 9706322ips 
map.size() = 16384 ->insert = 6460031ips find = 8290491ips 
map.size() = 32768 ->insert = 5733103ips find = 7280547ips 
map.size() = 65536 ->insert = 3968404ips find = 4712404ips 
map.size() = 131072 ->insert = 3182789ips find = 3379839ips 
map.size() = 262144 ->insert = 1886515ips find = 2179432ips 
map.size() = 524288 ->insert = 1768975ips find = 1947776ips 
map.size() = 1048576 ->insert = 1391089ips find = 1588497ips 
map.size() = 2097152 ->insert = 1309224ips find = 1438158ips 
map.size() = 4194304 ->insert = 1158693ips find = 1225254ips 
map.size() = 8388608 ->insert = 994051ips find = 993175ips 
map.size() = 16777216 ->insert = 822474ips find = 867235ips 
map.size() = 33554432 ->insert = 723948ips find = 719134ips
//hash
map.size() = 0 ->insert = 12083879ips find = 52726430ips 
map.size() = 1024 ->insert = 16687988ips find = 52885732ips 
map.size() = 2048 ->insert = 16063501ips find = 51553787ips 
map.size() = 4096 ->insert = 15725570ips find = 46866061ips 
map.size() = 8192 ->insert = 13953056ips find = 43241188ips 
map.size() = 16384 ->insert = 12607727ips find = 41356975ips 
map.size() = 32768 ->insert = 12238165ips find = 33896341ips 
map.size() = 65536 ->insert = 10665425ips find = 33263214ips 
map.size() = 131072 ->insert = 5790060ips find = 16269811ips 
map.size() = 262144 ->insert = 3660456ips find = 11894815ips 
map.size() = 524288 ->insert = 4720073ips find = 10094816ips 
map.size() = 1048576 ->insert = 3602543ips find = 9770919ips 
map.size() = 2097152 ->insert = 3487822ips find = 9448040ips 
map.size() = 4194304 ->insert = 3340267ips find = 9312065ips 
map.size() = 8388608 ->insert = 3235150ips find = 9278217ips 
map.size() = 16777216 ->insert = 3128011ips find = 9212153ips 
map.size() = 33554432 ->insert = 2919965ips find = 8505030ips 
 

Это size_t->size_t. Не совсем похоже на O(1).

0)Внутри общего алгоритма мы делаем некоторую операцию (сравнение/поиск по хэшу) при O(1) всегда 1 раз, при O(log(n)) от 1 до 64 раз.

Время этих операций нельзя приравнять друг другу. Одна может стоить в 64раза больше, чем те 64.

Длинна адресспейса на современной каменье - 48бит, длинна хеша 64бита. Я надеюсь ты сможешь почитать во сколько 64бита больше 48бит?

Если же взять физическую раму на той же каменье - это будет 39-48бит, реально же 48бит там никогда не будет, да и 39так же.

64раз там не будет никогда - от силы 25-30.

Не важно какая длина хэша.При бинарном дереве нам все равно придется повторить. 64 операции сравнения прежде чем гарантировнно найти элемент. Верно?

Уже 64. Я тебя уверяю, ещё до 30 твоя хештаблица не влезет ни в одну тачку на этом свете.

Быстрее/медленее - это конечно кол-во операций.

Быстрее/медленее - это время. Твои же O() - это коэффициент роста. Быстрее он или нет - никого не волнует на конечном, а уж тем более на реальном кол-ве n - особенно в сравнении 1 и 25.

В хэш таблице мы делаем всегда ОДНУ операцию.

Не всегда - это раз.

У тебя там «O(1)» из-за инварианта бакет на елемент == 1. Поддержка этого инварианта стоит настолько дожопы рамы, что там на 15лямах елментов уже 4гига, а на 30 уже все 10+. это на size_t->size_t. Хеш шире 32бит.

У бревна же это 16+16 байт на ноду * 15лямов 480метров. На 30лямов естественно никто не будет применять стльный хешмап - он слишком дерьмо для этого.

Если же взять реальные юзкейсы уровня тех, где хеш жрёт максиму гиг рамы.

Тут уже брёвна влезают в кеши, а это нивелирует разницу, либо выводит даже бревно вперёд. Но естественно такое убогое как стальное вряд-ли, но все же - потенциально может.

Это уж не говоря о новых кулл-разработках штеуда с л4 на сотню+метров.

В конечном итоге в реальном мире бревно не сильно отличается от хешмапы, особенно если ты не хочешь просрать 500метров рамы на десяток тысяч елементов.

Время этих операций нельзя приравнять друг другу. Одна может стоить в 64раза больше, чем те 64.

Да, я об этом тоже написал. Естественно мое утверждение верно при эквивалентности операций. Это очевидно.

Да, я об этом тоже написал. Естественно мое утверждение верно при эквивалентности операций. Это очевидно.

Ну только в реальном мире они не эквивалентны - этого достаточно. Что я могу с этим поделать? Никто не спорит, что 64>1, только в реальном мире там 25, и не 25 > 1, а 25 * {coef_0...coef_24} >< 1 * coef_b - уже от этого стоит плясать.

Вот мой бенчмарк - можешь запустить у себя и выкатить, ну и проверь заодно - не накосячил ли я там где-то. Можно потюнить хешмапу.

#include <iostream>
#include <unordered_map>
#include <functional>
#include <boost/range/irange.hpp>
#include <chrono>
#include <random>
#include <map>

using boost::irange;
using std::vector;
using std::chrono::system_clock;
using std::bind;
using namespace std::placeholders;
using hashmap_t = std::unordered_map<uint64_t, uint64_t>;
using map_t = std::map<uint64_t, uint64_t>;
using vptr_t = std::function<void(void)>;

double __call_time(const vptr_t & f) {
  auto start_time = system_clock::now();
  f();
  return std::chrono::duration<double>(system_clock::now() - start_time).count();
}

void print(double time, uint64_t n, char * str) {
  fprintf(stderr, "%s = %luips ", str, (uint64_t)(n / time));
}

void __call_n(const vptr_t & f, uint64_t n) {
  for(auto x : irange(0ul, n)) f();
}


int main(void) {
  hashmap_t map;
//   map_t map;
  vptr_t __insert = bind([&map](uint64_t n) {map.emplace(std::make_pair(n, n));}, bind(std::mt19937_64()));
  vptr_t __find = bind([&map](uint64_t n) {assert(map.find(n) != map.end());}, bind(std::mt19937_64()));
  for(uint64_t n = 1024; n != 1024 * 1024 * 128; n *= 2) {
    fprintf(stderr, "\nmap.size() = %lu ->", map.size());
    print(__call_time(bind(__call_n, __insert, n)), n, "insert");
    print(__call_time(bind(__call_n, __find, n)), n, "find");
  }
}

Вы это к чему?

У меня напротив Вашего профиля написано «хамоватое трепло». До сих пор актуально... идите в игнор, пожалуйста.

0) да.

1) нет. Если речь о доступе к элементу - зависит от того где этот элемент (кэш, рам, своп или вообще по сети шарится). Если речь идет об арифметике, зависит от того на конвейре ли операция. Модель вычислений, основанная на асимптотических оценках сложности алгоритмов, потеряла актуальность как только у компьютеров появилась память со сложной иерархией. Тем не менее про эту модель до сих пор лекции читают, статьи пишут и делают всякие глубокомысленные выводы, откуда нынешняя дискуссия и пошла. Сейчас вот roofline модель появилась, она значительно более адекватна, а все эти О(...) имеют лишь сугубо теоретический интерес как правило.

2) с точностью до п.1.

3) да, насколько я понимаю - не силен в реализации деревьев, их до черта видов есть. Но общий принцип такой.

4) не обязательно, зависит от реализации. Если тупо по битам делать то да, если оптимизировать то все те же log_2(n), при условии что дерево сбалансированно.

5)

... Так почему же они оба из твоих слов O(1)?

Потому что такое определение О(1)! Грубо, запись f(x) = O(g(x)) означает что f(x)<Cg(x), где С некоторая константа (хрен знает какая, важно что она существует). Если f(x) < C, то можно написать что f = O(1). Если при этом f<C g, то можно написать что f = O(g). И обе эти записи будут верными.

Я не шучу, там знак равенства это на самом деле не знак равенства а знак принадлежности к некоторому множеству.

Вот Вам небольшая иллюстрация - все (кто лекции не прогуливал), знают что сложность добавления элемента в список O(1), а в вектор O(N). ВОпрос, куда лучше набивать историю чего нить, в std::list<my_pod_type> или в std::vector<my_pod_type>? Где быстрее (в секундах) будет работать push_back()? При аллокаторах по умолчанию разумеется.

Даже стало интересно, сейчас тестик напишу, чтобы проерить правдивость слов о O(log(n)) для анордеред мапы.

Я Вам это предлагал два дня назад сделать, но Вы оскорбились;-)

Только я log(n) получил в 12м году, на старом процессоре и на довольно старой версии библиотеки, у меня был дебиан. С тех пор что то могло и поменяться, но все равно интересно.

Если речь о доступе к элементу - зависит от того где этот элемент (кэш, рам, своп или вообще по сети шарится)

Это мы вообще не затрагивали. Мы вообще не говорили о скорости работы в секундах на конкретных железках. Понятно, что это важно, но разговор был не о том.

И обе эти записи будут верными

Да я уже понял, что имелось в виду. Только вот алгоритмы не рассматривают с аппаратными ограничениями O(f(x)) оценивают при x=>бесконечности, а не при условиях x<=C. При последнем допущении ВСЕ алгоритмы на земле на реальных железках получается O(1). Но это смысла не имеет.

Вот Вам небольшая иллюстрация - все (кто лекции не прогуливал), знают что сложность добавления элемента в список O(1), а в вектор O(N). ВОпрос, куда лучше набивать историю чего нить, в std::list<my_pod_type> или в std::vector<my_pod_type>? Где быстрее (в секундах) будет работать push_back()? При аллокаторах по умолчанию разумеется.

Только вот вектор на деле это массив и если мы не попали на операцию после которой следует сделать ресайз массива, то как раз вектор будет O(1). Что может быть быстрее добавления в память по прямому адресу? В списке больше накладных расходов выйдет.

Я Вам это предлагал два дня назад сделать, но Вы оскорбились;-)

Я обиделся потому что я сразу сказал, что о секундах конкретных я не говорил. Я говорил лишь о теоретической, то есть не привязанной к железу и секундам оценке, т.е асимптотической оценке. Вот если сделать вывод в файл время на каждый инсерт для 1кк элементов, а потом построить график в гнуплоте, то это уже поинтереснее. Это будут не секунды, а зависимость по которым они растут.

Я такой тест и хочу запилить. Сегодня может сделаю. Делал более простой тест. Просто добавляю элемент (первый), замеряю времяя на его инсерт, добавляю 3кк элементов, добавляю еще элемент и замеряю его время.

Итог: std::map 15микросекунд и 220 микросекунд. std::unordered_map 17микросекунд и 18 микросекунд.

Как видим таки O(1) в чистом виде. Но таки запилю тест с графиками, так интеерснее.

Хм, гляну, спасибо.

Это мы вообще не затрагивали. Мы вообще не говорили о скорости работы в секундах на конкретных железках.

Простите, а какой смысл тогда вообще все это обсуждать? Меня не интересуют сферические вычислители в вакуме, даже если они розовые пони - меня интересует создание высокпроизводительных кодов работающих с большими массивами данных. Кроме того, Вы не имеете физически возможности простестировать абстрактный вычислитель, Вы можете только тестить конкретные железяки. Все остальное демагогия.

Только вот алгоритмы не рассматривают с аппаратными ограничениями O(f(x)) оценивают при x=>бесконечности, а не при условиях x<=C.

Это где так О_О? Все вычислительные алгоритмы вещи сугубо прикладные, и ес-но при их проектировании рассматривают аппартные ограничения, тем более что я про эти ограничения в каждом посте писал. Иначе че там - берем машину Тьюринга с бесконечной производительностью и бесконечной памятью и все проблемы решены.

В списке больше накладных расходов выйдет.

Правильно. Но только за счет того, что дефолтный аллокатор stl для вектора при пуше выделяет каждый раз памяти вдвое больше чем в прошлый. В итоге практика радикально отличается от теории с О(...).

Сергей, я говорил лишь про время доступа (поиска). С добавлением (то что Вы тестите) история совсем другая будет.

Число элементов нужно брать в широких пределах, так что бы в итоге оказалась занята почти вся память. Лучше взять логарифмическую шкалу.

Ну и в микросекундах это слишком грубо - нужно делать много операций. Желательно делать несколько измерений и выбирать минимальное время или среднее. Я таки сторонник минимального (в других случаях машина еще чем то занята была), но тут уж ладно, дело вкуса.

все (кто лекции не прогуливал), знают что сложность добавления элемента в список O(1), а в вектор O(N)

Сложность добавление по индексу в список так же O(n), а O(1) там только вставка в текущий(на который есть указатель) елемент. У пушбека там у обоих O(1).

Вот если сделать вывод в файл время на каждый инсерт для 1кк элементов, а потом построить график в гнуплоте, то это уже поинтереснее. Это будут не секунды, а зависимость по которым они растут.
время на каждый инсерт

Эксперты в треде. Я надеюсь тебе не надо объяснять почему это не работает?

Я такой тест и хочу запилить. Сегодня может сделаю. Делал более простой тест. Просто добавляю элемент (первый), замеряю времяя на его инсерт, добавляю 3кк элементов, добавляю еще элемент и замеряю его время.

Так это не «тестируется». Ты не можешь померить один insert() никак.

Итог: std::map 15микросекунд и 220 микросекунд. std::unordered_map 17микросекунд и 18 микросекунд.

Ты не то намерил. Такого просто не может быть. Особенно «микросекунд».

Как видим таки O(1) в чистом виде. Но таки запилю тест с графиками, так интеерснее.

Ты лучше запили тест, который что-то вменяемое выдаёт - я тебе гарантирую - твой тест выдаёт мусор.

Эксперты в треде. Я надеюсь тебе не надо объяснять почему это не работает?

да я догадывался, что это неверно. По идее погрешность измерений этих мс/мкс сопоставима со временем выполнения этого insert. Надо тестить для нескольких, я понимаю.

Ты не то намерил. Такого просто не может быть. Особенно «микросекунд».

Я сам удивился, но всякие clock() в разнице выдавали 0мс. Я думал, что это неверно, но писалось это посреди ночи, нормальный тест потом запилю.

Спасибо, дорогой, но это не отменяет того что вы пишете полнейшую ахинею.

В загромождении стандарта тоже ничего хорошего нет.

поржал

У пушбека там у обоих O(1).

ТОлько при условии, что вектору не надо заново выделять память.

обычным map лучше вообще не пользоваться, т. к. в нём O(log(n))

у unordered_map в среднем O(n)

Мне одному кажется, что ты поделил на ноль, т. к. log(n) < n?

(Кстати, ты ещё и ошибся фактологически, т. к. unordered_map на самом деле амортизированно O(1), а O(n) — это в худшем случае. Так что вывод у тебя правильный, но обоснование — чушь.)

То была опечатка, которую уже обсудили выше Динамический прямоугольный массив в Си++ (комментарий)