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

Дык и не сосите палец, это негигиенично.

Как Вы себе представляете доступ в разреженном массиве с ключом uint64_t за O(1)?

Хоть бы тесты какие потрудились погонять прежде чем высказываться.

Какой то rekt array получается. Ассоциативная структура с указателями для хранения примитивных последовательных данных.

представляете

Ещё раз для непонятливых: не надо ничего представлять. Надо читать стандарт. Там всё написано, в том числе про O(1) и про худший случай.

На самом деле надо универ не прогуливать. То что хэш таблица имеет O(1) скорость вставки/поиска говорят на первом/втором курсе, ну и чуть помедленее в случае коллизий(но этим можно пренебречь при хорошей хэш функции). Да и если ты знаешь как работает хэш-таблица, то должно быть очевидно, что O(1).

хехе, ректальные массивы Stahl'а

Это смотря какие у Вас цели. Если цели что бы работало, то одного чтения стандарта будет недостаточно. А есдли на лоре флудить, то конечно...

одного чтения стандарта будет недостаточно

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

http://www.boost.org/doc/libs/1_36_0/libs/numeric/ublas/doc/matrix.htm

Буст, да?
Нет, спасибо.

если это контейнер, то это скорее всего хедер-онли либа, ее скопировать bcp и там пара файлов hpp будет всего, имхо не так и страшно.

А еще говорят что кур доят.

Я повторяю вопрос - если хэш uint64_t, то каким образом для массива с таким ключем можно обеспечить доступ О(1)?

Когда закончите читать стандарт, скажите пожалуйста что будет работать быстрее (в секундах) - О(1) или O(log(n))?

Из лужи можете при этом не вылезать, если Вам там так нравится - сидите.

доступ О(1)

Тебе же сказали «в среднем».Если бы ты не проугливал универ, то знал бы что существуют коллизии, но при хорошей хэш функции и правильно выбранном размере массива они редки. И их наличием можно пренебречь. Тебе никто не говорил, что O(1) всегда, это ты выдумал.

А на сколько я понимаю это работает примерно так(во всяком случае это единственное здравое решение):

1. Берем массив длинной n, скажем 256, конкретное число не важно.
2. Массив хранит списки/векторы пар ключ/значение.
3. Берем хэш от ключа uint64_t и делаем hash % array_size -> индекс в массиве. Добавляем в список по этому адресу.
4. Если мы часто начинаем встречать коллизии, то увеличиваем размер массива в несколько раз и пересчитываем хэш-таблицу для каждой пары с hash % new_size

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

что будет работать быстрее (в секундах) - О(1) или O(log(n))?

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

Ну и к слову о секундах, я делал тест сравнение мап. Добавление в цикле 5000000 элементов в мапу-дерево 220 сек, в мапу хэш-таблицу 130. Поиск (ищем каждый ключ из вектора заранее подготовленных ключей-строк) 80/20 сек.

Коллизии пока что к делу не относятся.

Вас не смущает, что unordered_map работает с хэшем не один байт а восемь? Как Вы себе представляете жизнь в этом случае, берем хэш от хэша что бы обеспечить разумный размер массива?

Вас не смущает, что unordered_map работает с хэшем не один байт а восемь? Как Вы себе представляете жизнь в этом случае, берем хэш от хэша что бы обеспечить разумный размер массива?

Ничего не понял, объясни нормально. Да мы берем хэш, а потом остаток от деления хэша. Что тут не так?

Ой какой молодец! Дяденька, Вы еще погоняйте зависимость сокрости доступа для map<uint64_t> и unordered_map в зависимости от размера таблицы.

И, Сергей, мне не нравится Ваш тон. У себя в Нижнем будете ахинею таким тоном нести, а здесь не надо.

У себя в Нижнем будете ахинею таким тоном нести, а здесь не надо.

Во-первых не нижнем. Во-вторых не я первый начал

А еще говорят что кур доят.

и такое подобное. Если нужна культурная дискуссия, то возможно следует начать с себя?

Вы еще погоняйте зависимость сокрости доступа для map<uint64_t> и unordered_map

Ну а кто начал задавать вопрос уровня 1го курса универа, про разницу между O(1) и O(log(n)) в секундах

Мдя, кто то тут еще говрил про прогулы универа... смотрим сюда:

http://www.cplusplus.com/reference/unordered_map/unordered_map/

«Hash A unary function object type that takes an object of type key type as argument and returns a unique value of type size_t based on it.»

У меня size_t имеет размер 8 байт. Итак, мы получили ключ, взяли от этого ключа хэш, получили что то размерами size_t (причем оно ограниченно сверху лишь размером size_t) - дальше нам надо как то жить с этим size_t, поскольку скажем в вектор по нему не полезешь (у меня такой вектор в память не влезет).

Вы говорите - а фигня, давайте возьмем от этого хэша еще один хэш! Но тогда во первых радикально увеличивается вероятность коллизий, во вторых - а какой же все таки длины вектор сиит в unordered_map, как я могу посмотреть или изменить его длину? Ы?

Или там все таки не вектор?

Кур доят - это переход на личности? Ну ок.

То есть не хотите проверять зависимость скорсти доступа от размера таблицы? А зря, Вы бы таки увидидели тот самый log(n) для unordered_map, ну с точностью до уровней иерархии памяти. Я во всяком случае неск. лет назад, при аналогичной дискуссии, в тестах его видел.

Теперь Вам, с анонимусом, (как подающим себя, судя по тону, светилами ИТ вообще и оценок алгоритмеичской сложности в частности), вопрос - почему и O(1) (стандарт) и O(log(n)) (де-факто из тестов) для одного и того же контейнера верные оценки?

И какое это вообще имеет отношение к потребностям школоты вроде меня (раз Вы настаиваете что я школота - ну пусть)? У нас, школьников, потребности то прсотые - что бы работало побыстрее. В секундах;-)

а фигня, давайте возьмем от этого хэша еще один хэш!

Только вот операция % это не хэш.

Но тогда во первых радикально увеличивается вероятность коллизий,

Зависит от размерма входных данных. И не забывайте о рехэше.

во вторых - а какой же все таки длины вектор сиит в unordered_map, как я могу посмотреть или изменить его длину? Ы?

Документацию не читал, так и запишем. Открываем cplusplus.com первый -> unordered_map->constructor. И о боже! У первого же конструктра видем параметр «initial size»

n - Minimum number of initial buckets.

This is not the number of elements in the container, but the minimum number of slots desired for the internal hash table on construction. If this argument is not specified, the constructor determines this automatically (in a way that depends on the particular library implementation). Member type size_type is an unsigned integral type.

А зря, Вы бы таки увидидели тот самый log(n) для unordered_map, ну с точностью до уровней иерархии памяти.

Тесты пожалуйста в студию.

Кур доят - это переход на личности? Ну ок.

Ты еще и город перепутал.

Только вот операция % это не хэш.

Один из вариантов пострения хэш значения таки?

Виноват, я не специально. Но это было после того как Вы перешли на личности;-)

Унаследуйся от std::vector, переопредели operator [] чтобы возвращал промежуточный класс (допустим «строку» массива) и пользуйся на здоровье!

Кстати про оценку эффективности. Мой тест годиться только для общей оценки производительности, но никак не для оценки O(..). По хорошему тест надо делать так: Заполнить анордеред мап 2 элементами и сделать добавление. Потом заполнить 5000000 и добавить элемент и сравнить скорость добавление элемента. При этом тесты надо делать с разным наполнением. Ибо можно и на этот рехэш нарваться. Честно скажу, что не знаю как это работат в с++, но натыкался на такое обсуждение. Из которого следует, что хэш-таблица в яве работает как я сказал. И судя по доке по плюсам, то и тут должно работать так же.

http://stackoverflow.com/questions/10894558/how-hashtable-and-hashmap-key-val...

Один из вариантов пострения хэш значения таки?

Всего лишь часть вычисления индекса в конечном массиве. Хэш-функция дает нам равномерное распределение, а % дает нам попадаение в массив.

Операция (hash(key) % size_array - это все же O(1).

Текстовые индексы. (комментарий)

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

Насчет n в конструкторе - в тот раз мимо меня прошло, каюсь. Но я его не задавал тогда. М.б. если его задать будет классическая хэш таблица которую, Вы описывали, ХЗ.

Ну мы же не про добавление а про темп доступа пока.

Да кто бы спорил... но, так и быть уж - если n<2^64, то O(log_2(n))<O(64)=O(1), не так ли?;-)

А вот при профилировании ну совсем другая история.

но, так и быть уж - если n<2^64, то O(log_2(n))<O(64)=O(1), не так ли?;-)

Ничо не понял...

Чисто ради практического интереса использования фичей С++14 я тут накостылял обёртку для std::vector в виде stdx::matrix (пока без изменения размера как самостоятельной матрицы):

http://ideone.com/93dmgH

template<typename T, typename Allocator = std::allocator<T>>
class matrix_helper {
public:
    friend class matrix<T, Allocator>;

    using o_matrix = matrix<T, Allocator>;
    using p_vector = std::vector<T, Allocator>;
    using v_size_t = typename p_vector::size_type;

    typename p_vector::reference operator [] (v_size_t colindex) {
        return static_cast<p_vector &>(matrix_)[rowindex_ * matrix_.rowsize() + colindex];
    }

    operator typename p_vector::reference () {
        return static_cast<p_vector &>(matrix_)[rowindex_];
    }

    typename p_vector::reference operator = (T &&value) {
        return (typename p_vector::reference)(*this) = std::forward<T>(value);
    }

protected:
    matrix_helper(o_matrix &matrix, v_size_t rowindex) :
        matrix_(matrix),
        rowindex_(rowindex)
    {}
...
};

template <typename T, typename Allocator = std::allocator<T>>
class matrix : public std::vector<T, Allocator> {
public:
    using p_vector = std::vector<T, Allocator>;
    using v_size_t = typename p_vector::size_type;

    matrix(std::initializer_list<std::initializer_list<T>> contents)
    {
        for (auto &row : contents) {
            rowsize_ = row.size();
            p_vector::insert(p_vector::end(), row);
        }
    }

    v_size_t rowsize() const { return rowsize_; }

    matrix_helper<T, Allocator> operator [] (v_size_t rowindex) {
        return matrix_helper<T, Allocator>(*this, rowindex);
    }

private:
    v_size_t rowsize_ = invalid_size;
};

Хватит ныть, напиши сам. Там дел-то на пол дня.

Сергей, а какое у Вас образование, если не секрет?

Высшее. Но я никак не пойму что такое o(64)

В общем понятно, ты привел математические расчеты из которых вдруг всплыла O(64), то есть говоря простым языком выдуманна тобой эффективность, и ты ее привел к O(1) и теперь получается, что O(log_2(n)) внезапно эффективнее O(1). Еще раз повторяю вопрос - что такое O(64), я первый раз в жизни вижу такую сложность. Я желаю услышать ответ. Или слив будет засчитан. И без вопросов об образование, пожалуйста. Математика ваша ясна до

O(64)=O(1)

теперь получается, что O(log_2(n)) внезапно эффективнее O(1)

Мдя... Высшее какое именно? Вы же сами выше верно писали, что нельзя сранивать по эффективности O(1) и O(f(x)).

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

слив будет засчитан.

Ваш то, после этого пассажа - безусловно. Можете не продолжать.

Ваш то, после этого пассажа - безусловно. Можете не продолжать.

Может тогда я услышу объяснение про

если n<2^64, то O(log_2(n))<O(64)=O(1)

Я попросил тебя объяснить, что тут имелось в виду, а в ответ услышал вопрос про образование. Думаю, что как раз у тебя его нет. Не я несколькими постами выше спрашивал про секунды и не я писал выражение-сравнение в одной части которого логарифм, а в другой магическое O(64). Я третий раз спрашиваю, что такое O(64)? И что именно означает твое сравнение. Объясни, что означает логарифм в левой части, что такое O(64) (ну 64 то понятно, что log_2(2^64)==64, но я все еще не понимаю, что означает O(64) и почему у новой магической эффективности стоит равенство с O(1)). Я третий раз прошу тебя объяснить мне написанное, а ты третий раз увиливаешь, даже не пытаясь дать прямой ответ на прямой вопрос, что это как не слив?

Про асимптотические оценки - гуголь или хотя бы вики в помощь, изучайте до просветления.

А не я ставлю log(n) и O(1) в сравнение. Что за log(n)? я знаю, что деревья O(log(n)) а хэш-таблица O(1). Это f1(x) и f2(x). Почему у двух разных алгоримов стоит сравнение? Это ты сравниваешь их. И я так и не услышал ответа почему из результата log_2(n)(n<=2^64) следует магическое O(64) из котороо следует O(1). Это в твоей формуле следует что log(n) быстрее o(1)

ты прямым текстом написал

O(log_2(n))<O(64)=O(1)

что O(log(n)<O(1). А потом еще смеешь спрашивать меня про образования и обвинять меня в сравнение разных функций? У тебя прямым текстом написанно что O(log(n)) быстрее O(1)

У тебя прямым текстом написанно что O(log(n)) быстрее O(1)

Где? Процитируйте пожалуйста, где я утверждал что «O(log(n)) БЫСТРЕЕ O(1)»? Ну или где я утверждал, что «O(log(n)) МЕДЛЕННЕЕ O(1)»?

Объясни, что означает логарифм в левой части

Алгоритмическая сложность бинарного поиска (поиска по бинарному дереву).

Математика ваша ясна до O(64)=O(1)

Вас в гугле забанили совсем?

https://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое

«Основновные свойства: ... O(C \cdot f) = O(f)»

Конечно запись O(log_2(n))<=O(64) с математической точки зрения не корректна, мне лень было вдаваться в интимные подробности, но поскольку log_2(n)<=64 при n<=2^64, можно сказать что log_2(n)=O(1) при n<2^64. Это прямое следствие определения О(...) (см. вики например).

Другими словами, можно утверждать, что при конечной длине хэша и бинарном дереве, в котором ключем является хэш а значением букет (да-да, это тоже хэш таблица), сложность доступа к букету О(1). На самом деле там O(log_2(N)), но в силу ограниченности N это одно и то же.

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

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

Как же это знакомо - «школьник, неучился, доказываешьчтоO(1)медленнеlogn».

http://codeforces.com/blog/entry/4710

Для очередного объекта номер bucket'а, куда он попадёт, вычисляется как Hash(x) % bucket_count()

Я примерно о том же и говорил, чуть другая реализация. Но суть примерно та же.

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

Судя по его аватарке, манере общения и непроходимой тупости - РАН не зря убили.

Судя по его аватарке, манере общения и непроходимой тупости - РАН не зря убили.

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

На самом деле там O(log_2(N)), но в силу ограниченности N это одно и то же.

Так, упрощу вопросы. Остальное все сейчас удалю. Мне не надо ответов на другие. Для начала я скажу, что отлично понимаю, что время выполнения и алгоритмическая сложность разные вещи. Что можно хэш считать дольше, чем весь бинарный поиск. Когда я говорил быстрее/медленее я имел в виду именно алгоритмическую сложность. Прошу простить меня за мой кривой термин.

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

1) O(1) - операция (общий поиск) занимает всегда одно и то же время. при 1 элементе сажем 1сек (1 сек допустим занимает 1 подоперация из (0)) и при 2^64 1 сек. Верно?

2) O(log_2(n) означает что время выполнение операции завист от размера даных. при одной операции 1 сек(одна операция в 1сек), при 2^64 - 64 сек(64 операции по секунде). Верно?

3) Бинарное дерево поиска подразумевает сравнение текущей ноды. и обход дерево бинарно откидывая одну из веток.Верно?

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

5)

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

Вычисли́тельная сло́жность — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных

Быстрее/медленее - это конечно кол-во операций. Само собой при O(1) мы проделываем только вычисление хэша + доступ к элементу. При поиске по бинарному дереву, нам надо проводить операцию сравнения до 64 раз. Получатся в дереве мы делаем одну операцию сравнения при 1 элементе и 64 при 2^64. В хэш таблице мы делаем всегда ОДНУ операцию. Так почему же они оба из твоих слов O(1)? Или ты не это имел в виду и я уже второй день спорю ибо неверно понял посыл?

Я говорю что твой собеседник туп. Ты все правильно говоришь.