powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Быстрый поиск поля в массиве в С
15 сообщений из 65, страница 3 из 3
Быстрый поиск поля в массиве в С
    #39770214
jenya7
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonjenya7не понял вопроса? проблема в скорости поиска элемента. table1 и table2 это статическая память в РАМ.
я получил данные
table1.items[0].reference_number = 100
table1.items[0].priority_level = 0
------------------------------------------
table1.items[11].reference_number = 111
table1.items[11].priority_level = 11

в этот момент я перебираю все элемены в table2 и ищу совпадение table2[i].reference_number == table1.items[j].reference_number
нашел? table2[i].priority_level == table1.items[j].priority_level
вся проблема в быстроте поиска. это единственная проблема.
в случае с хэш таблицей нужно учитывать что элементы в table2 могут быть удалены и выделенная память в хэш таблице не освободиться.
Блинн. Почему с тобой так сложно? Почему ты решил что это есть проблема? Я не просто так спросил
про доступную память. Потому что СУЩЕСТВУЮТ хеш таблички которые работают не ре-аллоцируя
память. Но для этого им нужно дать чуть больше памяти (1.5-2 раза) чем твои элементы. ПОЭТОМУ
я нудным голосом спрашиваю тебя еще раз - Сколько памяти можно выделить в твоём микро-контроллере
или ХЗ в чем-то еще!

Женя. Дорогой. Отвечай на вопросы экспертов. Если ты не отвечаешь - то можно сделать вывод
что помощь тебе не нужна. И ты просто пришел сюда от скуки.
В принципе занести в хэш таблицу нам нужно 12 элементов. Даже если нужно памяти в два раза больше - 24 элемента, конечно там есть. Это не слабый микроконтролер у него 128 Мега РАМ.
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770235
jenya7
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
извиняюсь. ошибся. это если бы было определенное количество ключей (reference_number). если придет элемент с другим ключем то нужно добавлять элемент в хэш таблицу.
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770237
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
jenya7В принципе занести в хэш таблицу нам нужно 12 элементов. Даже если нужно памяти в два раза больше - 24 элемента, конечно там есть. Это не слабый микроконтролер у него 128 Мега РАМ.
В английской википедии по HashTable описан метод открытой адресации.

https://en.wikipedia.org/wiki/Hash_table#Open_addressing

Можешь его использовать. Экспериментально подбери размер чтоб для твоих данных не было ни одной коллизии.
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770241
jenya7
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonjenya7В принципе занести в хэш таблицу нам нужно 12 элементов. Даже если нужно памяти в два раза больше - 24 элемента, конечно там есть. Это не слабый микроконтролер у него 128 Мега РАМ.
В английской википедии по HashTable описан метод открытой адресации.

https://en.wikipedia.org/wiki/Hash_table#Open_addressing

Можешь его использовать. Экспериментально подбери размер чтоб для твоих данных не было ни одной коллизии.
спасибо. попробую.
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770309
jenya7
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
вобщем сделал такой ход конем

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
typedef struct 
{
    int key;
    int value;
    int used;
} HT_NODE;

HT_NODE nodes[NODES_COUNT][NODE_SIZE] = { 0 };

int HASHTBL_GetIndex(int key)
{
    return (key % NODES_COUNT);
}


int HASHTBL_Push(int key, int value) 
{
    //get a node number
    int node_num = HASHTBL_GetIndex(key);
    int idx = 0, unused_idx, first = 0;
    
    //scan all node elements
    while (idx < NODE_SIZE)
    {
        //used elements - if the same key - rewrite
        if (nodes[node_num][idx].used)
        {
            if (nodes[node_num][idx].key == key)
            {
                nodes[node_num][idx].value = value;
                return UPDATED;
            }
        }
        else
        {
           if (!first)
           {
               first =  1;
               //remember the first unused element
               unused_idx = idx;  
           }
        }
        idx++;
    }  
    
    //the same key not found - insert it in the first empty slot
    nodes[node_num][unused_idx].key = key;
    nodes[node_num][unused_idx].value = value;
    nodes[node_num][unused_idx].used = 1;
    
    return NEW;
}


int HASHTBL_Pop(int key) 
{
    int node_num = HASHTBL_GetIndex(key);
    int idx = 0;
    
    //scan all node elements
    while (idx < NODE_SIZE)
    {
        if (nodes[node_num][idx].used)
        {
            if ( nodes[node_num][idx].key == key )
            {
                nodes[node_num][idx].used = 0;
                return nodes[node_num][idx].value;
            }
        }
        
        idx++;
    }
    
    return NOT_FOUND;
}




нужно только оптимально настроить количество узлов и их глубину.
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770315
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Посмотри еще как хешируют целые числа
https://en.wikipedia.org/wiki/Universal_hashing#Hashing_integers
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770318
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Может я не врубаюсь в проблему, но мне кажется, что проблема "...обновляются асинхронно.....за время поиска....." решается корректным многозадачным программированием (блокировками, copy-on-write и так далее) и никакой алгоритм поиска, хоть в цикле, хоть hash'ем, хоть через ж..., хоть через гланды - никак ситуацию изменить не может

IMHO & AFAIK
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770321
Swa111
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
jenya7,

хеш таблица на 12 элементов не имеет смысла, дольше будете вычислять хеши, даже последовательное чтение 12 элементов будет быстрее. Если уж и делать хеш то для таблицы 512 элементов. Тогда нужно будет вычислить всего 12 хешей.
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770323
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Поиск в массиве из двух элементов обычно идет быстрее чем в хеш табличке из двух этих-же
элементов. Это я не ради троллинга сказал. А просто такова есть природа вещей. Иногда
мы используем хеш-таблички просто потому что верим в них.
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770377
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton...обычно идет быстрее.....
Какая разница: быстрее/медленнее ?

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


Где-то в Инете
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
Core i7 Xeon 5500 Series Data Source Latency (approximate)               [Pg. 22]

local  L1 CACHE hit,                              ~4 cycles (   2.1 -  1.2 ns )
local  L2 CACHE hit,                             ~10 cycles (   5.3 -  3.0 ns )
local  L3 CACHE hit, line unshared               ~40 cycles (  21.4 - 12.0 ns )
local  L3 CACHE hit, shared line in another core ~65 cycles (  34.8 - 19.5 ns )
local  L3 CACHE hit, modified in another core    ~75 cycles (  40.2 - 22.5 ns )

remote L3 CACHE (Ref: Fig.1 [Pg. 5])        ~100-300 cycles ( 160.7 - 30.0 ns )

local  DRAM                                                   ~60 ns
remote DRAM                                                  ~100 ns
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770382
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если люди работают с сетевым протоколом то ожидание готовности следующего
сетевого пакета будет настолько недетерминированным и говорить о наносекундах
будет настолько странно как если-бы мы с вами говорили о личной гигиене во времена
короля Людовика 14. Зачем говорит о том чего нет. И какой смысл ускорять хендлинг
данных в наносекунды если лаг сетей меряется милисекундами. Это цифры не того порядка.

Хотя может у автора там другая шина. Не эзернет...

Был лет 5 назад один чел с ником Студентик/Базист. Если помните.
Он строил ин-мемори ДБМС с наносекундным откликом. А адаптеры к ней писал на дотнете.
Вобщем... нагромождение нелепиц. Хотя с ним было нескучно.
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770386
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

да ТС пока даже не удосужился ответить "кто ложит данные", "кто забирает данные" без учёта этого решать то, что он навыдумывал вообще бессмысленно
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770390
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
21801729 )))
21802617 "вся проблема в быстроте поиска. это единственная проблема." ( C ) )))))))))

mayton...о личной гигиене во времена короля Людовика 14....
"дорогая, я возврашаюсь из Египта, не мойся" ( C ) Наполион - Жозефине )))
не дословно, с чужих слов, ссылку на архивные материалы привести не могу
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770395
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да. Французы это еще те пакостники. Не в обиду им будь сказано. По поводу "разных источников".
Принят и обработать - не одно и то-же. Никто не запрещает автору их просто складывать в кольцевой буфер
и обрабатывать по мере возможности. На прерываниях там... или на континуэйшенах или хер ево знает
как этот АРМ работает. Не знаю. Но я вобщем щас нарушаю своё собственное правило в топиках...
Начинаю додумывать за автора его задачу.

А он - скуп на слова. Мдя... Может дипломную работу делает. Эдакий стесняшка..
...
Рейтинг: 0 / 0
Быстрый поиск поля в массиве в С
    #39770413
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Offtopic "про Людовика XIV":


где-то-в-Инете...
К минимальной обязательной ежедневной гигиене в 16-18 веках относилось умывание рук, лица и ног. Водой. И чем холоднее, тем лучше. Этому учили с детства. За обеденным столом у знати стояли плошки с душистой водой и полотенца – чтобы перед едой сполоснуть руки. Но, как во все времена, люди были более чистоплотные и менее чистоплотные.

Рот споласкивали водой, а зубы чистили деревянными палочками. В Европе зубная щетка появилась в 50-х годах XVI века. Уже в 1728 г. знаменитый французский врач Фошар в руководстве по зубоврачеванию указывал о применении зубной щетки из щетины. Для усиления очищающего действия зубной щетки издавна применяли различные порошки: пепел, поваренную соль. Конечно, зубы у многих были плохие.
...
Людовик XIV
...
Герцог Сен-Симон описывает, что тело короля по утрам растирали лосьоном из роз и затем насухо полотенцем и меняли рубашку. Один из слуг умывал королю руки смесью воды и вина. Людвиг XIV полностью менял гардероб 3-4 раза в день – после охоты, после прогулки, после бала. И каждый раз ему подавали свежее белье и растирали его с головы ло пят спиртовым лосьоном из роз или лаванды. Таким образом, он был одним из самых чистых людей своей эпохи.

И ванны Людовик XIV принимал. Но он в них .....не мылся, а принимал их с лечебными целями, с целью расслабиться, а также для интимных встреч с фаворитками...Его подданные старались копировать его во всем. При Людовике XIV в Версале было около 100 мобильных ванн. Король не разрешал устанавливать в Версале стационарные ванны. Исключением был он сам. Сам Людовик XIV был единственным в Версале, кто имел не мобильные, а стационарные «купальные апартаменты - «appartements de bains», состоявшие из трех помещений, с теплой водой.
....

Купальные аппартаменты Людовика XIV в Версале (восьмиугольная ванна изображена красным цветом).

Вот что осталось от ванных аппартаментов Людовика XIV: восьмиугольная ванна из лангедокского мрамора. Эта ванна «короля-солнца» прошла через многие руки, одно время была в собственности Мадам де Помпадур, затем Наполеона. А теперь стоит в оранжерее Версаля. Раньше стены ванны украшали фигуры дельфинов и русалок. Но новому королю Людовику XV помещения понадобились для своей дочери – Версаль постоянно перестраивался. И „appartements de bains" были разрушены. Сейчас эта ванна стоит в Оранжерее Версаля.


Франция, XVII век, Неизвестный художник. Женщина принимает ванну с чашкой шоколада


Bidet / биде изобрели и впервые стали применять во Франции в 17м веке. В переводе это слово обозначает «маленькая лошадка»




Модератор: Тема перенесена из форума "Программирование".
...
Рейтинг: 0 / 0
15 сообщений из 65, страница 3 из 3
Форумы / C++ [игнор отключен] [закрыт для гостей] / Быстрый поиск поля в массиве в С
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]