Оптимизация линейного поиска

@Raptor1232 · Регистрация: 08.02.2021

Студворк — интернет-сервис помощи студентам

Здравствуйте, хотел спросить, каким методом лучше оптимизировать линейный поиск. И считается ли оптимизацией поиск с двух сторон? Вроде этого:

C++
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
srand(time(NULL));
const int SIZE = 40;
 
int key; // from user
int count = 0;
 
int arr[SIZE]; // array
int indices[SIZE] = {};
 
for (int i = 0; i < SIZE; ++i)
{
    arr[i] = rand() % 30;
}
 
cout << "\n\nEnter your key: ";
cin >> key;
 
for (int i = 0, j = SIZE - 1; i < SIZE / 2, j >= SIZE / 2; ++i, --j)
{
    if (arr[i] == key)
    {
        indices[count] = i;
        count++;
    }
        
    if (arr[j] == key)
    {
        indices[count] = j;
        count++;
    }
}

@OpXiv · 08.02.2021, 20:40

Сообщение от zayats80888

Там из Compiler Explorer есть ссылка на бенчмарк, по которой можно перейти и потестить код.

Кланг кстати быстрее выполняет код!)

https://quick-bench.com/q/5Pqe... hek5CgJcOQ

Надо выкинуть ГЦЦ

....

Ну вот, теперь ещё компилятор надо учитывать, на каком быстрее будет выполняться.

@SmallEvil · 08.02.2021, 20:50

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

Сообщение от oleg-m1973

Есть еще Алгоритм Гровера

Verevkin · 08.02.2021, 20:53

вы маньяки.

Кликните здесь для просмотра всего текста

@SmallEvil · 08.02.2021, 20:54

Сообщение от Verevkin

Многопоточностью.

Ну разве что до количества ядер, больше потоков тоже не поможет.
Потому как находятся все значения а не первое. Все равно надо все перебрать.

@oleg-m1973 · 08.02.2021, 20:57

Сообщение от SmallEvil

Потому как находятся все значения а не первое. Все равно надо все перебрать.

В смысле? Каждый поток перебирает только свой кусок массива. Соответственно, скорость увеличится пропорционально количеству ядер/процессоров.

@OpXiv · 08.02.2021, 21:19

Сообщение от SmallEvil

через указатели будет быстрей

На кол его, если он так думает. Быстрее точно не будет, ибо получиться тоже самое.

@VTsaregorodtsev · 08.02.2021, 21:31

Сообщение от OpXiv

Его вообще будет ещё медленнее, потому что каждый цикл FOR он выполняет 2 раза операцию деления на 2

Компиляторы давно уже умеют оптимизировать константные выражения прямо на этапе компиляции. Т.е. из SIZE / 2 компилятор сделает (и будет использовать) новую константу ==> делений на этапе выполнения не будет вообще.
Также компиляторы давно уже заменяют /2 на быструю операцию сдвига на один бит вправо - это если у ТСа при переделке кода SIZE станет переменной, а не константой.

Сообщение от OpXiv

Его мега крутая

Ну и где там команды деления?

@OpXiv · 08.02.2021, 21:39

Сообщение от VTsaregorodtsev

Ну и где там команды деления?

Как бы там не было, мой вариант работает за 64 секунды. Его вариант работает за 103
https://quick-bench.com/q/5Pqe... hek5CgJcOQ

Это на 39 медленнее. От как

@oleg-m1973 · 08.02.2021, 21:42

Сообщение от OpXiv

Как бы там не было, мой вариант работает за 64 секунды. Его вариант работает за 103

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

@OpXiv · 08.02.2021, 21:42

Сообщение от oleg-m1973

Все уже давно поняли, кроме тебя.

Я изначально говорил что его вариант плохой. Ты что - то путаешь.

@zayats80888 · 08.02.2021, 21:46

Сообщение от OpXiv

Ну вот, теперь ещё компилятор надо учитывать, на каком быстрее будет выполняться.

Ты бы хоть посмотрел, какую оптимизацию сделал clang

Он в одном проходе сразу по два элемента из массива загружает.

@OpXiv · 08.02.2021, 21:48

Сообщение от zayats80888

Ты бы хоть посмотрел, какую оптимизацию сделал clang

Посмотрел. Увидел что, если не стараться писать оптимизации, компилятор за тебя сделает оптимизацию. И сделает это гораздо лучше.

@oleg-m1973 · 08.02.2021, 21:50

Сообщение от zayats80888

Ты бы хоть посмотрел, какую оптимизацию сделал clang Он в одном проходе сразу по два элемента из массива загружает.

Кстати, а ведь я говорил

Сообщение от oleg-m1973

Ещё, наверное, можно считать сразу два элемента твоего массива в 64-битную локальную переменную и сравнить её половины с ключом. По идее должно будет быстрее отрабатывать, во всяком случае на x64

@zayats80888 · 08.02.2021, 22:19

Сообщение от OpXiv

Увидел что, если не стараться писать оптимизации, компилятор за тебя сделает оптимизацию. И сделает это гораздо лучше.

Это правильно. Но такую оптимизацию можно и самому сделать.
Для такого цикла, например, получим тот же самый код

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
for (int i = 0; i < SIZE; i += 2)
{
    if (arr[i] == key)
    {
        indices[count] = i;
        count++;
    }
    if (i < SIZE - 1 && arr[i + 1] == key)
    {
        indices[count] = i + 1;
        count++;
    }
}

@oleg-m1973 · 08.02.2021, 22:29

Сообщение от zayats80888

Для такого цикла, например, получим тот же самый код

Разве тот же? Мне казалось, что здесь должно быть что-то наподобие

C++
1
2
3
4
for (int i = 0; i < SIZE / 2; ++i)
{
    uint64_t x = reinterpret_cast<uint64_t *>(arr)[i];
         //if (low(x) == key || high(x) == key)

Добавлено через 2 минуты

Сообщение от zayats80888

i < SIZE - 1

А это должно проверятся один раз после цикла, а не на каждой итерации

Verevkin · 08.02.2021, 23:39

Сообщение от SmallEvil

Ну разве что до количества ядер, больше потоков тоже не поможет.
Потому как находятся все значения а не первое. Все равно надо все перебрать.

Посмотри это.

Новые блоги и статьи Все статьи Все блоги /
Нейтральные знания ..., ... чистая наука. Пока что-то проходит модерацию на Хабре, стоит развить мысль ... Hrethgir 20.07.2026 К таким радикальным взглядам я конечно в той публикации не приходил, но чтобы скоротать вечер, решил углубиться немного. 1. Почему показания термометра заряжены целью? Цель заложена в самом. . .	Установка нескольких штампов электронной подписи в строго определенных местах файла docx ВладимирСамохин 19.07.2026 (В!) Работа с Электронной подписью - это неотъемлемая часть современного документооборота. Но что делать, если нужно поставить несколько штампов электронной подписи в строго определенных местах. . .	сукцессия 35. Научная статья о проделанной работе anaschu 19.07.2026 Написал в формате латекс и пдф	Вангую, что это не пройдёт модерацию, и на неделе я запущу свой сервер. Hrethgir 19.07.2026 Эта публикация сейчас в песочнице и ждёт приглашения. https:/ / habr. com/ ru/ sandbox/ 295048/ По ссылке 403. Не очень информативно такую ссылку постить. Запись от Usaga размещена Сегодня в 06:46 . . .
сукцессия 33. открытые вопросы от клауде anaschu 19.07.2026 "Что накопилось за эту часть А — тринадцать правок, из которых шесть пришли из ваших вопросов и каждая оказалась реальной ошибкой, а не калибровкой: односторонний симбиоз, отсутствующий листопад,. . .	32 сукцессия anaschu 19.07.2026 сукцессия 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не «подкручивает» сходимость —. . .	сукцессия 31: модель микоризы - это модель ещё нескольких явлений, социальных и экономических anaschu 18.07.2026 Теория «Всего»: апдейт v1. 1. 2 — 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не. . .	сукцессия 30. Массив проверяющих друг друга моделей anaschu 18.07.2026 Архитектура сети взаимопроверяющих моделей микоризной сукцессии (v2. 0) Развитие тензорного ОДУ-ядра и создание кросс-платформенного калибровочного полигона Уважаемые коллеги! В продолжение. . .

Verevkin Злостный нарушитель 10878 / 5817 / 1288 Регистрация: 12.03.2015 Сообщений: 26,855
	08.02.2021, 20:53
	вы маньяки. Кликните здесь для просмотра всего текста 0