1866 / 766 / 105
Регистрация: 01.10.2012
Сообщений: 4,138
|
|
17.06.2013, 16:35 | 121 |
Ответ кодом часто лучший, но здесь форыч не в масть, речь идет о быстром поиске, а не линейном переборе
Какой угодно, используйте любые средства Вашего языка, сторонние либы тоже можно. Цвет - ну хотя бы uint32. Что-то долго раскачиваетесь
0
|
17.06.2013, 16:35 | |
Ответы с готовыми решениями:
1010
Какой язык программирования лучше? Какой язык программирования лучше? (3) Какой язык программирования лучше для создания игры??? Какой язык программирования мне ст0ит учить? |
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
|
||||||
17.06.2013, 17:14 | 122 | |||||
Просто LOL. Возьмём хеш-таблицу с ключами по цветам. Временная эффективность поиска O(1)
Поставленная задача полностью решена. Жду код на Си (ясный и прекрасный код) с бОльшей или такой же эффективностью. Добавлено через 15 минут За O(1) достаточно "быстрый" поиск?
0
|
4539 / 2732 / 486
Регистрация: 28.04.2012
Сообщений: 8,630
|
||||||
17.06.2013, 17:16 | 123 | |||||
А если так
0
|
Ушел с форума
|
||||||
17.06.2013, 17:16 | 124 | |||||
Да нет проблем:
0
|
1866 / 766 / 105
Регистрация: 01.10.2012
Сообщений: 4,138
|
|
17.06.2013, 17:21 | 125 |
Не сачкуйте. Дан исходный контейнер, нужны хеш-таблицы - делайте их (а не "возьмем"). И реультат печатайте. Совсем распустились на "прогрессивных" языках.
Поверьте, эффективность там намного больше, а про расход памяти/ресурсов и говорить неудобно Но сначала намекну: Вы решаете задачу "найти все с данным цветом". Это не совсем то что сказано в условии - и это маленькое отличие многое меняет.
0
|
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
|
|
17.06.2013, 17:22 | 126 |
По plist'у поиск линейный. Но на малых объёмах будет быстрее чем хеш-таблица.
Но ведь об объёме входных данных и о том, что такое "быстрый" поиск ничего не сказано. Фактически очередная сферическая задача в вакууме от Igor3D.
0
|
4539 / 2732 / 486
Регистрация: 28.04.2012
Сообщений: 8,630
|
|
17.06.2013, 17:25 | 127 |
А, точно, ну да ладно.
Ты же сам сказал, что «любой», я вот сразу прикинул и решил изначально хранить в хеш-таблице. =)
0
|
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
|
|
17.06.2013, 17:26 | 128 |
Я чего-то упустил? Мне было предложено выбрать любой контейнер, я взял хеш-таблицу? ЧЯДНТ?
Блин, улыбнуло.
0
|
4539 / 2732 / 486
Регистрация: 28.04.2012
Сообщений: 8,630
|
|
17.06.2013, 17:27 | 129 |
Ну так надо как-то сразу выбирать подходящий контейнер, обычно ж так делают, не?
0
|
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
|
|
17.06.2013, 17:28 | 130 |
Хех, ты просто жжёшь В некой реализации на Си временная эффективность поиска лучше чем O(1).
Я хочу это видеть! Код в студию
0
|
4539 / 2732 / 486
Регистрация: 28.04.2012
Сообщений: 8,630
|
|
17.06.2013, 17:28 | 131 |
Прям таки намного? Быстрее, чем O(1)? Не, допустим хеш-функция в CL не так быстро сумму считает, но уж прям чтобы намного, как-то не верится.
0
|
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
|
||||||
17.06.2013, 17:42 | 132 | |||||
Задача решена полностью в соответствии с условием.
Добавлено через 12 минут Ну разве что за исключением того, как представлен элемент. Ну, скажем, можно его представить в виде cons ячейки.
Это рояли никакой не играет.
0
|
1866 / 766 / 105
Регистрация: 01.10.2012
Сообщений: 4,138
|
|
17.06.2013, 17:50 | 133 |
Вполне нормальное решение на плюсах, но все-таки 2 двоичных поиска, а можно обойтись вообще без поисков. Также механизм не очень общий - напр может быть не разрешено менять порядок элементов в исходном контейнере (пусть это др задача - но все же). Тогда создавать/таскать доп. ассоциативный контейнер накладно.
Не спешите, подумайте. Свою версию выложу завтра
0
|
4226 / 1796 / 211
Регистрация: 24.11.2009
Сообщений: 27,562
|
|
17.06.2013, 17:54 | 134 |
В контейнере как ни запоминай, что где валяется, а придёшь к необходимости поиска уже этих записей. Если только не стоит задача доступа по индексу.
0
|
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
|
||||||
17.06.2013, 18:34 | 135 | |||||
Чтобы не потерять взаимосвязь между названиями и цветами, можно задать элементы как alist и для поиска за O(1) предварительно сформировать хеш-таблицу. Это тривилаьно и на CL это будет выглядить так:
0
|
Ушел с форума
|
|
17.06.2013, 18:38 | 136 |
Зачем делать готовое ?
Язык предоставляет реализации, значит логично использовать их, если только нет каких-то совершенно исключительных противопоказаний. Я таких противопоказаний пока не встречал. Свою реализацию красно-черного или AVL-дерева писать не вижу смысла: вопрос обогнать (думаю, что ближе к истине - не догнать) Dinkumware/STLPort не стоит, тем более, что скорость работы программ в большей степени упирается в правильную алгоритмизацию, а не в детали ее имплементации. А обосновать ? Забыли ? На всякий случай выделил жирным: Согласен, быстрее было бы multiset::equal_range. Разве только если сразу напечатать printf-ом вывод программы, без всяких item-ов и поисков. Этого не было в условии задачи. Контейнер не сортирован - линейный поиск. Сортирован - двоичный. Оба варианта были приведены, оба наглядны, переносимы и опираются исключительно на стандартные средства языка. Ваш ход.
0
|
1866 / 766 / 105
Регистрация: 01.10.2012
Сообщений: 4,138
|
|
17.06.2013, 19:05 | 137 |
В условии сказано "каждый элемент имеет цвет" но не "каждому цвету уже соответствует набор элементов". Если такая структура образуется по ходу дела - пожалуйста, но ее надо создать из исходного контейнера, а не брать с потолка.
Я никак не призывал к "фанатичной оптимизации", тем более тягаться с известными контейнерами. Решение детское и место ему в разделе для начинающих, но оно без поисков, правда. Мы (в известной мере) в плену шаблонов/стандартных решений, т.к. точно знаем "это работает". Но это не всегда лучшее. Шо за нетерплячка? Сказал же - завтра, даю время подумать и применить все "самое прогрессивное".
0
|
Ушел с форума
|
|
17.06.2013, 19:24 | 138 |
"Есть массив/контейнер элементов, каждый из которых имеет цвет".
Контейнер есть (vector/multiset), элемент тоже (item), каждый элемент имеет (has-a) цвет (color). Решение соответствует той детализации задачи, с которой она была поставлена. Дальше уже придирки, не имеющие отношения к теме C vs C++. Ваше решение настолько прогрессивное, что его нельзя написать за 5 минут ?
0
|
4866 / 3288 / 468
Регистрация: 10.12.2008
Сообщений: 10,570
|
||||||
17.06.2013, 20:44 | 139 | |||||
Код
[guest@localhost cont]$ .ansi t.c -o t [guest@localhost cont]$ ./t 1: 123 3: 789 5: 100 [guest@localhost cont]$
0
|
0 / 0 / 0
Регистрация: 04.04.2013
Сообщений: 14
|
|
17.06.2013, 23:00 | 140 |
за Delphi где голосуют?
0
|
17.06.2013, 23:00 | |
17.06.2013, 23:00 | |
Помогаю со студенческими работами здесь
140
Какой язык лучше / прибыльнее? Какой язык веб-программирования выбрать? Плюсы\минусы Какой язык лучше изучать с нуля? Какой язык лучше изучать C или C++ Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |