1911 / 773 / 108
Регистрация: 01.10.2012
Сообщений: 4,214
|
|
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
|
4544 / 2738 / 486
Регистрация: 28.04.2012
Сообщений: 8,648
|
||||||
17.06.2013, 17:16 | 123 | |||||
А если так
0
|
Ушел с форума
|
||||||
17.06.2013, 17:16 | 124 | |||||
Да нет проблем:
0
|
1911 / 773 / 108
Регистрация: 01.10.2012
Сообщений: 4,214
|
|
17.06.2013, 17:21 | 125 |
Не сачкуйте. Дан исходный контейнер, нужны хеш-таблицы - делайте их (а не "возьмем"). И реультат печатайте. Совсем распустились на "прогрессивных" языках.
Поверьте, эффективность там намного больше, а про расход памяти/ресурсов и говорить неудобно Но сначала намекну: Вы решаете задачу "найти все с данным цветом". Это не совсем то что сказано в условии - и это маленькое отличие многое меняет.
0
|
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
|
|
17.06.2013, 17:22 | 126 |
По plist'у поиск линейный. Но на малых объёмах будет быстрее чем хеш-таблица.
Но ведь об объёме входных данных и о том, что такое "быстрый" поиск ничего не сказано. Фактически очередная сферическая задача в вакууме от Igor3D.
0
|
4544 / 2738 / 486
Регистрация: 28.04.2012
Сообщений: 8,648
|
|
17.06.2013, 17:25 | 127 |
А, точно, ну да ладно.
Ты же сам сказал, что «любой», я вот сразу прикинул и решил изначально хранить в хеш-таблице. =)
0
|
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
|
|
17.06.2013, 17:26 | 128 |
Я чего-то упустил? Мне было предложено выбрать любой контейнер, я взял хеш-таблицу? ЧЯДНТ?
Блин, улыбнуло.
0
|
4544 / 2738 / 486
Регистрация: 28.04.2012
Сообщений: 8,648
|
|
17.06.2013, 17:27 | 129 |
Ну так надо как-то сразу выбирать подходящий контейнер, обычно ж так делают, не?
0
|
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
|
|
17.06.2013, 17:28 | 130 |
Хех, ты просто жжёшь В некой реализации на Си временная эффективность поиска лучше чем O(1).
Я хочу это видеть! Код в студию
0
|
4544 / 2738 / 486
Регистрация: 28.04.2012
Сообщений: 8,648
|
|
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
|
1911 / 773 / 108
Регистрация: 01.10.2012
Сообщений: 4,214
|
|
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
|
1911 / 773 / 108
Регистрация: 01.10.2012
Сообщений: 4,214
|
|
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++ Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи | |||||
Как настроить CI/CD с помощью Jenkins
InfoMaster 15.01.2025
Введение в CI/ CD и Jenkins
В современной разработке программного обеспечения непрерывная интеграция (CI) и непрерывная доставка (CD) стали неотъемлемыми элементами процесса создания качественных. . .
|
Как написать микросервис на Go/Golang с Kafka и GitHub CI/CD
InfoMaster 14.01.2025
Определение микросервиса, преимущества использования Go/ Golang
Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .
|
Как написать микросервис с нуля на C# с RabbitMQ, CQRS и CI/CD
InfoMaster 14.01.2025
В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .
|
Как создать интернет-магазин на PHP и JavaScript
InfoMaster 14.01.2025
В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .
|
Как написать Тетрис на Ассемблере
InfoMaster 14.01.2025
Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .
|
Как создать игру "Танчики" на Unity3d и C#
InfoMaster 14.01.2025
Разработка игр – это увлекательный процесс, сочетающий в себе творчество и технические навыки. В этой статье мы рассмотрим создание классической игры "Танчики" с использованием Unity3D и языка. . .
|
Организую платный онлайн микро-курс по доработке Android-клиента Telegram
_Ivana 14.01.2025
Официальная версия и распространенные форки не полностью устраивают? Сделай свою кастомную версию клиента!
4 занятия по 2 часа (2 недели пн, ср 19:00-21:00 по Москве).
Первое вводное занятие. . .
|
Как создать приложение для фитнеса для iOS/iPhone на Kotlin
InfoMaster 14.01.2025
Создание собственного фитнес-приложения — это не только захватывающий, но и полезный процесс, ведь оно может стать вашим верным помощником на пути к здоровому и активному образу жизни. В современных. . .
|
Как создать приложение магазина для iOS/iPhone на Swift
InfoMaster 14.01.2025
Введение в разработку iOS-приложений
Разработка приложений для iPhone и других устройств на базе iOS открывает огромные возможности для создания инновационных мобильных решений. В данной статье мы. . .
|
Это работает. Скорость асинхронной логики велика. Вопрос видимо останется в стабильности. Плата - огонь!
Hrethgir 13.01.2025
По прошлому проекту в Logisim Evolution https:/ / www. cyberforum. ru/ blogs/ 223907/ blog8781. html прилагаю файл архива проекта в Gowin Eda. Восьмибитный счётчик из сумматора+ генератор сигнала. . .
|
UserScript для подсветки кнопок языков программирования в зависимости от текущего раздела
volvo 13.01.2025
В результате работы этого скрипта подсвечиваются нужные кнопки не только в форме быстрого ответа, но и при редактировании сообщения:
/ / ==UserScript==
/ / @name CF_DefaultLangSelect
/ / . . .
|
Введение в модели и алгоритмы машинного обучения
InfoMaster 12.01.2025
Машинное обучение представляет собой одну из наиболее динамично развивающихся областей искусственного интеллекта, которая фокусируется на разработке алгоритмов и методов, позволяющих компьютерам. . .
|