The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]




Версия для распечатки Пред. тема | След. тема
Новые ответы [ Отслеживать ]
Как быть с массивами, !*! Dimitry, 24-Сен-06, 14:33  [смотреть все]
Приветствую!

Немного о проблеме:
Есть 2 строковых массива с ID число элементов 1000, длинна строки 15 символов. (строки одного массива уникальны)
Пр.
a[1]="stringone_a";
b[1]="stringone_b";
...
a[1000]="string1000_a";
b[1000]="string1000_b";
Это только пример, систематики у строк нет!

Программа скажем так в течении 1сек получает 10-20 var1 и var2 для сравнения строк

//этот код выполняется 20 раз в сек  
for(i=1;i<1001;i++) {
if(strcmp(a[id],var1)==0 && strcmp(b[id], var2)==0) //делаем что надо, около 20 совпадений за цикл
}

Что у нас получается, за секунду около 20*2*1000 = 40 000 сравнений строк средней длинной 10 символов

Так вот это ведь тоже нагрузка, можно её избежать в СИ++?
Например в ПХП или перле я бы работал с хеш-массивами и 40 000 сравнений отпало бы )

id=hash[var12];
if(id) //do it

Надеюсь меня кто нить поймёт ) Вообщем какие варианты есть по оптимизации, может как то работать с классами? Или есть возможность в С++ использовать хеши?? Я ничего не нашёл :/

  • Как быть с массивами, !*! v.i.t, 18:52 , 24-Сен-06 (1)
    В С++  это называется  Ассоциативный массив  (template<class K, class V> class Map)
  • Как быть с массивами, !*! DeadMustdie, 19:29 , 24-Сен-06 (2)
    C++ опирается на стандартные библиотеки.
    Древовидный "ассоциативный массив" реализуется шаблоном std::map.
    Собственно хеш-таблица вроде бы была реализована каким-то шаблоном boost,
    плюс многие реализации STL содержат шаблон std::hash_map.

    Кстати, хеш-таблицу при необходимости недолго и несложно изготовить руками.
    Если, конечно, понимать, как она работает и за счет чего ускрояется поиск.

    • Как быть с массивами, !*! Dimitry, 22:12 , 24-Сен-06 (3)

      >Кстати, хеш-таблицу при необходимости недолго и несложно изготовить руками.
      >Если, конечно, понимать, как она работает и за счет чего ускрояется поиск.
      >
      Это ты хорошо сказал =) Видимо хеши не такие быстрые как массивы.

      Спасибо, кое что накопал, думаю поможет.

      • Как быть с массивами, !*! DeadMustdie, 10:45 , 25-Сен-06 (4)
        >Это ты хорошо сказал =) Видимо хеши не такие быстрые как массивы.

        Собственно, хеш изготавливается вокруг "классического" массива со специальной
        индексацией, основанной на хеш-функции поверх ключа
        ;)




Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру