Easyelectronics.ru

Электроника для всех
Текущее время: 23 сен 2019, 06:01

Часовой пояс: UTC + 5 часов



JLCPCB – Прототипы печатных плат за $2/10pcs (Любой цвет!)
Крупнейший производитель печатных плат и прототипов. Более 600000 клиентов и свыше 10000 заказов в день!
Получите скидку на почтовую отправку при первом заказе в JLCPCB!

Начать новую тему Ответить на тему  [ Сообщений: 60 ]  На страницу Пред.  1, 2, 3
Автор Сообщение
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 22:09 
Старожил
Аватара пользователя

Зарегистрирован: 27 мар 2015, 04:10
Сообщения: 1931
Откуда: Харьков
UnКаЙF писал(а):
alexsam писал(а):
Почему массив быстрее чем список

Мы всегда знаем где элемент Element_max/2.
Соответственно, начинаем поиск в нужной subполовине массива. [Всё-таки изучите алгоритмы и структуры данных]

Я имел ввиду скорость прохода по массиву и списку.
По структурам данным все отлично, спасибо :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 25 янв 2018, 22:33 
Старожил

Зарегистрирован: 19 мар 2013, 19:37
Сообщения: 2619
Откуда: Санкт-Петербург
alexsam,
С ключами ситуация с оверхедом изменится, появится смысл держать сортированный массив указателей на данные (и половинное деление будет работать, и двигать при сортировке мало).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 26 янв 2018, 02:27 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 849
alexsam
С точки зрения обхода всех элементов список и массив одинаковы.
Но у вас был запрос на скорость поиска.

Сложность алгоритма поиска для списка O(n) (на самом деле, O(n/2)... Но я этого не говорил...)
Сложность алгоритма поиска для отсортированного массива O(log2(n))

Для массива длиной 100 элементов это означает, что вместо 100 максимальных (или, скорее 50 что соответствует матожиданию) итераций, вы получите результат уже через 6.
6 против 50-ти - это хорошая оптимизация.


Последний раз редактировалось Mirmik 26 янв 2018, 02:37, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 26 янв 2018, 02:29 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 849
Для справки, сложность поиска по идеальной хэштаблице O(1). Что означает получение результатат на первой же итерации.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 26 янв 2018, 02:49 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 849
Отвечая на вопрос, как так получается, что оно быстрее:
В отличие от списка, вы всегда можете рассчитать, где в массиве расположен центральный элемент. Вы сразу смотрите его значение. Поскольку ваш массив отсортирован вы знаете, что все элементы справа от центрального имеют адрес выше, а все элементы слева - адрес ниже, чем искомый.
Допустим искомый адрес меньше адреса центрального элемента. Мы мгновенно заключаем, что ни один из элементов в правой половине не содержит нужного объекта. Мы с ходу отбраковали 50 элементов. Следующим шагом из оставшейся половины мы отбракуем ещё 25. потом ещё 12 и так на 6-ом шаге придем к результату.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 26 янв 2018, 04:23 
Заглядывает иногда

Зарегистрирован: 19 дек 2017, 08:12
Сообщения: 139
Откуда: SPb
Mirmik писал(а):
Отвечая на вопрос, как так получается, что оно быстрее:

А вот неоднозначно :)
Т.е., оно ЖЕЛЕЗНО быстрее - если в массиве мульён элементов.
Или - если массив хранится на диске, и для сравнения мне надо каждый элемент в память подтягивать.
Или - если длина ключа ну хотя бы в сотню байтов.
В нашем случае ни одно из перечисленного и близко не лежало.
Есть предположение, что 50 (матожидание) оборотов "тупого" цикла "сравнение 2-х байтов, приращение адреса" может оказаться ДЕШЕВЛЕ 6 оборотов алгоритма двоичного поиска :))) Число элементов - как раз такое, что оно где-то "на грани", так что дать строгий ответ про "быстрее" можно только реализовав оба алгоритма и посчитав число тактов МК для обоих :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 26 янв 2018, 12:51 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 849
Проанализировал этот вопрос. Согласен. Поиск обходом, вероятно может оказаться предпочтительнее.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 26 янв 2018, 12:54 
Старожил
Аватара пользователя

Зарегистрирован: 11 апр 2016, 18:04
Сообщения: 2373
Откуда: Китай, Пекин
Mirmik писал(а):
Проанализировал

в смысле код в железо написал? и какие результаты?

_________________
unirail.org


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 26 янв 2018, 13:58 
Старожил
Аватара пользователя

Зарегистрирован: 24 июл 2012, 13:54
Сообщения: 849
Нет. Посчитал операции. Для полной ясности действительно стоило бы написать.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Организация массива данных в памяти и поиск по параметру
СообщениеДобавлено: 31 янв 2018, 19:07 
Здравствуйте!

Зарегистрирован: 31 янв 2018, 19:04
Сообщения: 2
список для вашего случая не лучший выбор. оптимальнее использовать Hash. Изображение


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 60 ]  На страницу Пред.  1, 2, 3

Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB