Хэш-таблица vs. дерево поиска - Философия программирования

Здравствуйте, WolfHound, Вы писали:

WH>Ничего не понял. Что не реально? Хеш посчитать не реально?

Посчитать хеш неупорядоченной коллекцииза O(1) нереально, нужно O(N), причём значение хеш-функции не должно зависеть от порядка аргументов (в голову приходит только xor)
Сравнить две неупорядоченные коллекции за O(N) не реально, нужно O(N*log(N)). Причём сравнение реально пишеться и работает, а вот написать хорошую хеш-фунцию, значение которой не зависит от порядка элементов коллекции это интересная задачка. Xor это бомба замедленного действия. Возможно имеет смысл делить достаточно большое число последовательно на все элементы и что-то делать с результатом и остатками

Тут вообще надо подумать.

Здравствуйте, alexeiz, Вы писали:

A>Для малого количества элементов hash функция не имеет большого значения.

Малое — это сколько?

Здравствуйте, adontz, Вы писали:

A>Посчитать хеш неупорядоченной коллекцииза O(1) нереально, нужно O(N), причём значение хеш-функции не должно зависеть от порядка аргументов
А что посчитать хеш упорядоченой коллекции за O(1) можно?
A>(в голову приходит только xor)
Плохо.
A>Сравнить две неупорядоченные коллекции за O(N) не реально, нужно O(N*log(N)).
Если это хеш таблици с веременем поиска O(1) то еще как реально.
A>Причём сравнение реально пишеться и работает, а вот написать хорошую хеш-фунцию, значение которой не зависит от порядка элементов коллекции это интересная задачка. Xor это бомба замедленного действия. Возможно имеет смысл делить достаточно большое число последовательно на все элементы и что-то делать с результатом и остатками

Тут вообще надо подумать.
У меня ни разу не получалось написать совсем плохую хеш функцию.

... << RSDN@Home 1.1.4 beta 6a rev. 436>>

Здравствуйте, vdimas, Вы писали:

V>Здравствуйте, alexeiz, Вы писали:

A>>Для малого количества элементов hash функция не имеет большого значения.

V>Малое — это сколько?

Где-то до 100.

Здравствуйте, alexeiz, Вы писали:

A>Где-то до 100.
stdext::hash_set, видимо, далеко не самая удачная реализация хештаблицы. Если кому-нибудь интересно, вот тесты, накиданные на коленке за 5 минут:
Тестируем 100000 итераций, на каждой примерно 50 случайных вставок и 50 случайных поисков. Во всех случаях компилируем VC++/C# 2005 Release.

std::set                                 1593
stdext::hash_set                         2047

Wintellect.PowerCollections.Set          1328
Wintellect.PowerCollections.OrderedSet   1890

Так, хештаблица в .NET оказывается быстрее дерева в native C++, которое оказывается быстрее дерева в .NET. Кстати, один из вариантов ускорения деревьев в .NET более-менее ясен: использовать бинарный предикат сравнения вместо тернарного.

Исходники:

using System;
using Wintellect.PowerCollections;


delegate void Tester();

class MyRandom
{
    int seed;

    public int Next()
    {
        seed = (int) (seed * 214013L + 2531011L);
        return (seed >> 16) & 0x7fff;
    }
}

class Test
{
    static void InvokeTest(Tester tester, string comment)
    {
        int timer0 = Environment.TickCount;
        tester();
        int timer1 = Environment.TickCount;
        Console.WriteLine("{0,-40} {1}", comment, timer1 - timer0);
    }
        
    const int N_OPS = 100;
    const int N_ITERATIONS = 100000;
    
    static void Main()
    {
        InvokeTest(
            delegate
            {
                MyRandom random = new MyRandom();
                Set<int> s  = new Set<int>();
                for (int i = 0; i < N_ITERATIONS; i++)
                {
                    s.Clear();
                    for (int j = 0 ;j < N_OPS; j++)
                    {
                        if (random.Next() % 2 == 0)
                        {
                            s.Add(random.Next());
                        }
                        else
                        {
                            s.Contains(random.Next());
                        }
                    }
                }
            },
            "Wintellect.PowerCollections.Set");
            
        InvokeTest(
            delegate
            {
                MyRandom random = new MyRandom();
                OrderedSet<int> s  = new OrderedSet<int>();
                for (int i = 0; i < N_ITERATIONS; i++)
                {
                    s.Clear();
                    for (int j = 0 ;j < N_OPS; j++)
                    {
                        if (random.Next() % 2 == 0)
                        {
                            s.Add(random.Next());
                        }
                        else
                        {
                            s.Contains(random.Next());
                        }
                    }
                }
            },
            "Wintellect.PowerCollections.OrderedSet");
    }
}

#include <set>
#include <hash_set>
#include <stdlib.h>
#include <time.h>

class MyRandom
{
    int seed;
    
public:    
    MyRandom()
        : seed(0)
    {
    }
    
    int Next()
    {
        seed = (int) (seed * 214013L + 2531011L);
        return (seed >> 16) & 0x7fff;
    }
};

const int N_OPS = 100;
const int N_ITERATIONS = 100000;


template <class T>
void InvokeTest(const T& tester, char* comment)
{
    int t1 = clock();    
    tester.Run();
    int t2 = clock();    
    int time = t2 - t1;
    printf("%-40s %10d\n", comment, time);
}


template <class S>
class Tester
{
public:
    void Run() const
    {
        S s;
        MyRandom random;
        
        for (int i = 0; i < N_ITERATIONS; i++)
        {
            s.clear();
            for (int j = 0 ;j < N_OPS; j++)
            {
                if (random.Next() % 2 == 0)
                {
                    s.insert(random.Next());
                }
                else
                {
                    s.find(random.Next());
                }
            }
        }
    }
};

int main()
{
    InvokeTest(Tester<std::set<int> >(), "std::set");
    InvokeTest(Tester<stdext::hash_set<int> >(), "stdext::hash_set");
}

Здравствуйте, vdimas, Вы писали:

V>Кстати, несмортя на то, что вопрос не плохой, стоит сделать акцент на том, что удовлетворение всех вовсе не обязательно. Т.е. для кого-то эти массивы равны, если рассматриваются как множества, а для кого-то нет. Действительно, для некоторых задач предпочтительней map-ы, основанные на отношении порядка. Это никак не противоречит тому, что для других задач отношение порядка по боку.

Ага. И если вернуться к вопросу реализации switch-а, то казалось бы зачем для этого упорядычивание?