Форум программистов, компьютерный форум, киберфорум
Священные войны
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.88/336: Рейтинг темы: голосов - 336, средняя оценка - 4.88
1866 / 766 / 105
Регистрация: 01.10.2012
Сообщений: 4,138
17.06.2013, 16:35 121
Author24 — интернет-сервис помощи студентам
Цитата Сообщение от Убежденный Посмотреть сообщение
Реализация на чистом C++11 :
Ответ кодом часто лучший, но здесь форыч не в масть, речь идет о быстром поиске, а не линейном переборе

Цитата Сообщение от nullxdth Посмотреть сообщение
Давайте Каким образом должен быть представлен цвет? Какой именно контейнер допустимо взять?
Какой угодно, используйте любые средства Вашего языка, сторонние либы тоже можно. Цвет - ну хотя бы uint32. Что-то долго раскачиваетесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.06.2013, 16:35
Ответы с готовыми решениями:

Какой язык программирования лучше?
Какой на ваш взгляд самый универсальный(т.е. одинаково хорош во всех сферах программирования: веб,...

Какой язык программирования лучше? (3)
Продолжение темы

Какой язык программирования лучше для создания игры???
Какой язык программирования лучше для создания игры, С++ или С#???

Какой язык программирования мне ст0ит учить?
... оканчивю мат. школу, и хочу поступить на программиста. Программирую (неплохо) на Паскале. Что...

1010
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
17.06.2013, 17:14 122
Цитата Сообщение от Igor3D Посмотреть сообщение
Какой угодно, используйте любые средства Вашего языка, сторонние либы тоже можно. Цвет - ну хотя бы uint32. Что-то долго раскачиваетесь
Просто LOL. Возьмём хеш-таблицу с ключами по цветам. Временная эффективность поиска O(1)
Lisp
1
2
3
4
5
6
(defparameter *content* (plist-hash-table '(:red   (:a :b :c)
                                            :green (:d :e)
                                            :blue  (:f :g :h :i))))
 
(gethash :green *content*)              ; * (:D :E)
(gethash :blue  *content*)              ; * (:F :G :H :I)
Лишь стандратная библиотека CL (+ функция plist-hash-table из alexandria).
Поставленная задача полностью решена. Жду код на Си (ясный и прекрасный код) с бОльшей или такой же эффективностью.

Добавлено через 15 минут
Цитата Сообщение от Igor3D Посмотреть сообщение
речь идет о быстром поиске, а не линейном переборе
За O(1) достаточно "быстрый" поиск?
0
Эксперт функциональных языков программированияЭксперт Java
4539 / 2732 / 486
Регистрация: 28.04.2012
Сообщений: 8,630
17.06.2013, 17:16 123
А если так
Lisp
1
2
3
4
5
6
(psetf (get 'red   :items) '(:a :b :c)
       (get 'green :items) '(:d :e)
       (get 'blue  :items) '(:f :g :h :i))
 
(get 'red  :items) ; (:A :B :C)
(get 'blue :items) ; (:F :G :H :I)
?
0
Ушел с форума
Эксперт С++
16478 / 7441 / 1187
Регистрация: 02.05.2013
Сообщений: 11,617
Записей в блоге: 1
17.06.2013, 17:16 124
Цитата Сообщение от Igor3D Посмотреть сообщение
Ответ кодом часто лучший, но здесь форыч не в масть, речь идет о быстром поиске, а не линейном переборе
Да нет проблем:
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <algorithm>
#include <iostream>
#include <set>
 
 
 
enum color {red, blue, green};
 
 
 
struct item
{
    item(int Val, color Clr) : Value(Val), Color(Clr) {}
 
    int     Value;
    color   Color;
 
    bool operator <(item const &Item) const
    {
        return (Color < Item.Color);
    }
};
 
 
 
int main()
{
    typedef std::multiset<item> container_t;
 
    container_t Colors;
 
    Colors.insert(item(123, red));
    Colors.insert(item(456, blue));
    Colors.insert(item(789, red));
    Colors.insert(item(15,  green));
    Colors.insert(item(100, red));
    Colors.insert(item(55,  blue));
 
    item ItemToFind(0, red);
 
    container_t::const_iterator itBegin = Colors.lower_bound(ItemToFind);
    container_t::const_iterator itEnd   = Colors.upper_bound(ItemToFind);
 
    std::for_each(itBegin, itEnd, [&](item Item){std::cout << Item.Value << std::endl;});
 
    return 0;
}
Вывод:
123
789
100
Да, и я по-прежнему жду эквивалентной реализации на С.
0
1866 / 766 / 105
Регистрация: 01.10.2012
Сообщений: 4,138
17.06.2013, 17:21 125
Цитата Сообщение от nullxdth Посмотреть сообщение
Просто LOL. Возьмём хеш-таблицу с ключами по цветам.
Не сачкуйте. Дан исходный контейнер, нужны хеш-таблицы - делайте их (а не "возьмем"). И реультат печатайте. Совсем распустились на "прогрессивных" языках.

Цитата Сообщение от nullxdth Посмотреть сообщение
Жду код на Си (ясный и прекрасный код) с бОльшей или такой же эффективностью.
Поверьте, эффективность там намного больше, а про расход памяти/ресурсов и говорить неудобно
Но сначала намекну: Вы решаете задачу "найти все с данным цветом". Это не совсем то что сказано в условии - и это маленькое отличие многое меняет.
0
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
17.06.2013, 17:22 126
Цитата Сообщение от korvin_ Посмотреть сообщение
А если так
Код Lisp
1
2
3
4
5
6
(psetf (get 'red * :items) '(:a :b :c)
* * * *(get 'green :items) '(:d :e)
* * * *(get 'blue *:items) '(:f :g :h :i))
(get 'red *:items) ; (:A :B :C)
(get 'blue :items) ; (:F :G :H :I)
?
По plist'у поиск линейный. Но на малых объёмах будет быстрее чем хеш-таблица.
Но ведь об объёме входных данных и о том, что такое "быстрый" поиск ничего не сказано. Фактически очередная сферическая задача в вакууме от Igor3D.
0
Эксперт функциональных языков программированияЭксперт Java
4539 / 2732 / 486
Регистрация: 28.04.2012
Сообщений: 8,630
17.06.2013, 17:25 127
Цитата Сообщение от nullxdth Посмотреть сообщение
По plist'у поиск линейный.
А, точно, ну да ладно.

Цитата Сообщение от Igor3D Посмотреть сообщение
Не сачкуйте. Дан исходный контейнер
Ты же сам сказал, что «любой», я вот сразу прикинул и решил изначально хранить в хеш-таблице. =)
0
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
17.06.2013, 17:26 128
Цитата Сообщение от Igor3D Посмотреть сообщение
Не сачкуйте. Дан исходный контейнер, нужны хеш-таблицы - делайте их (а не "возьмем").
Цитата Сообщение от Igor3D Посмотреть сообщение
Какой угодно, используйте любые средства Вашего языка, сторонние либы тоже можно.
Я чего-то упустил? Мне было предложено выбрать любой контейнер, я взял хеш-таблицу? ЧЯДНТ?
Цитата Сообщение от Igor3D Посмотреть сообщение
И реультат печатайте.
Блин, улыбнуло.
0
Эксперт функциональных языков программированияЭксперт Java
4539 / 2732 / 486
Регистрация: 28.04.2012
Сообщений: 8,630
17.06.2013, 17:27 129
Цитата Сообщение от Igor3D Посмотреть сообщение
Но сначала намекну: Вы решаете задачу "найти все с данным цветом". Это не совсем то что сказано в условии - и это маленькое отличие многое меняет.
Ну так надо как-то сразу выбирать подходящий контейнер, обычно ж так делают, не?
0
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
17.06.2013, 17:28 130
Цитата Сообщение от Igor3D Посмотреть сообщение
Поверьте, эффективность там намного больше, а про расход памяти/ресурсов и говорить неудобно
Хех, ты просто жжёшь В некой реализации на Си временная эффективность поиска лучше чем O(1).
Я хочу это видеть! Код в студию
0
Эксперт функциональных языков программированияЭксперт Java
4539 / 2732 / 486
Регистрация: 28.04.2012
Сообщений: 8,630
17.06.2013, 17:28 131
Цитата Сообщение от Igor3D Посмотреть сообщение
Поверьте, эффективность там намного больше
Прям таки намного? Быстрее, чем O(1)? Не, допустим хеш-функция в CL не так быстро сумму считает, но уж прям чтобы намного, как-то не верится.
0
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
17.06.2013, 17:42 132
Цитата Сообщение от Igor3D Посмотреть сообщение
Но сначала намекну: Вы решаете задачу "найти все с данным цветом". Это не совсем то что сказано в условии - и это маленькое отличие многое меняет.
Задача решена полностью в соответствии с условием.

Добавлено через 12 минут
Цитата Сообщение от nullxdth Посмотреть сообщение
Задача решена полностью в соответствии с условием.
Ну разве что за исключением того, как представлен элемент. Ну, скажем, можно его представить в виде cons ячейки.
Lisp
1
'(:a . :red)
Ну и извлечь cdr перед непосредственным поиском.
Это рояли никакой не играет.
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
Цитата Сообщение от Igor3D Посмотреть сообщение
Вполне нормальное решение на плюсах, но все-таки 2 двоичных поиска, а можно обойтись вообще без поисков.
В контейнере как ни запоминай, что где валяется, а придёшь к необходимости поиска уже этих записей. Если только не стоит задача доступа по индексу.
0
2304 / 1063 / 77
Регистрация: 12.03.2013
Сообщений: 4,987
17.06.2013, 18:34 135
Чтобы не потерять взаимосвязь между названиями и цветами, можно задать элементы как alist и для поиска за O(1) предварительно сформировать хеш-таблицу. Это тривилаьно и на CL это будет выглядить так:
Lisp
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
(defparameter *content* '((:a . :red)
                          (:b . :red)
                          (:c . :red)
                          (:d . :green)
                          (:e . :green)
                          (:f . :blue)
                          (:g . :blue)
                          (:h . :blue)
                          (:i . :blue)))
 
(defun compound-hash-table (content)
  (let ((ht (make-hash-table)))
    (mapc #'(lambda (item)
              (let ((title (car item))
                    (color (cdr item)))
                (push title (gethash color ht))))
          content)
    ht))
 
(let ((content (compound-hash-table *content*)))
  (format t "~&~A~&~A"
          (gethash (cdr (assoc :d *content*)) content)
          (gethash (cdr (assoc :b *content*)) content)))
 
;; STDOUT:
;; (E D)
;; (C B A)
А также, никакой реализации на Си мы пока не увидели
0
Ушел с форума
Эксперт С++
16478 / 7441 / 1187
Регистрация: 02.05.2013
Сообщений: 11,617
Записей в блоге: 1
17.06.2013, 18:38 136
Цитата Сообщение от Igor3D Посмотреть сообщение
Дан исходный контейнер, нужны хеш-таблицы - делайте их (а не "возьмем").
Зачем делать готовое ?
Язык предоставляет реализации, значит логично использовать их, если только нет
каких-то совершенно исключительных противопоказаний. Я таких противопоказаний пока
не встречал. Свою реализацию красно-черного или AVL-дерева писать не вижу смысла:
вопрос обогнать (думаю, что ближе к истине - не догнать) Dinkumware/STLPort не стоит,
тем более, что скорость работы программ в большей степени упирается в правильную
алгоритмизацию, а не в детали ее имплементации.

Цитата Сообщение от Igor3D Посмотреть сообщение
Поверьте, эффективность там намного больше, а про расход памяти/ресурсов и говорить неудобно
А обосновать ? Забыли ?


Цитата Сообщение от Igor3D Посмотреть сообщение
Вы решаете задачу "найти все с данным цветом". Это не совсем то что сказано в условии - и это маленькое отличие многое меняет.
На всякий случай выделил жирным:
Цитата Сообщение от Igor3D Посмотреть сообщение
Есть массив/контейнер элементов, каждый из которых имеет цвет (color). Надо быстро найти все с тем же цветом что и данный элемент
Цитата Сообщение от Igor3D Посмотреть сообщение
Вполне нормальное решение на плюсах, но все-таки 2 двоичных поиска
Согласен, быстрее было бы multiset::equal_range.

Цитата Сообщение от Igor3D Посмотреть сообщение
а можно обойтись вообще без поисков.
Разве только если сразу напечатать printf-ом вывод программы, без всяких item-ов и поисков.

Цитата Сообщение от Igor3D Посмотреть сообщение
Также механизм не очень общий - напр может быть не разрешено менять порядок элементов в исходном контейнере
Этого не было в условии задачи.
Контейнер не сортирован - линейный поиск. Сортирован - двоичный. Оба варианта были приведены,
оба наглядны, переносимы и опираются исключительно на стандартные средства языка.
Ваш ход.
0
1866 / 766 / 105
Регистрация: 01.10.2012
Сообщений: 4,138
17.06.2013, 19:05 137
Цитата Сообщение от Убежденный Посмотреть сообщение
Зачем делать готовое ?
Язык предоставляет реализации, значит логично использовать их, если только нет
каких-то совершенно исключительных противопоказаний. Я таких противопоказаний пока
не встречал.
В условии сказано "каждый элемент имеет цвет" но не "каждому цвету уже соответствует набор элементов". Если такая структура образуется по ходу дела - пожалуйста, но ее надо создать из исходного контейнера, а не брать с потолка.

Цитата Сообщение от Убежденный Посмотреть сообщение
Свою реализацию красно-черного или AVL-дерева писать не вижу смысла:
вопрос обогнать (думаю, что ближе к истине - не догнать) Dinkumware/STLPort не стоит,
тем более, что скорость работы программ в большей степени упирается в правильную
алгоритмизацию, а не в детали ее имплементации.
Я никак не призывал к "фанатичной оптимизации", тем более тягаться с известными контейнерами. Решение детское и место ему в разделе для начинающих, но оно без поисков, правда. Мы (в известной мере) в плену шаблонов/стандартных решений, т.к. точно знаем "это работает". Но это не всегда лучшее.

Цитата Сообщение от nullxdth Посмотреть сообщение
А также, никакой реализации на Си мы пока не увидели
Шо за нетерплячка? Сказал же - завтра, даю время подумать и применить все "самое прогрессивное".
0
Ушел с форума
Эксперт С++
16478 / 7441 / 1187
Регистрация: 02.05.2013
Сообщений: 11,617
Записей в блоге: 1
17.06.2013, 19:24 138
Цитата Сообщение от Igor3D Посмотреть сообщение
В условии сказано "каждый элемент имеет цвет" но не "каждому цвету уже соответствует набор элементов". Если такая структура образуется по ходу дела - пожалуйста, но ее надо создать из исходного контейнера, а не брать с потолка.
"Есть массив/контейнер элементов, каждый из которых имеет цвет".

Контейнер есть (vector/multiset), элемент тоже (item), каждый элемент
имеет (has-a) цвет (color). Решение соответствует той детализации задачи, с
которой она была поставлена. Дальше уже придирки, не имеющие отношения к
теме C vs C++.

Цитата Сообщение от Igor3D Посмотреть сообщение
Сказал же - завтра, даю время подумать и применить все "самое прогрессивное".
Ваше решение настолько прогрессивное, что его нельзя написать за 5 минут ?
0
4866 / 3288 / 468
Регистрация: 10.12.2008
Сообщений: 10,570
17.06.2013, 20:44 139
Цитата Сообщение от Убежденный Посмотреть сообщение
Хочу увидеть эквивалентный код на C.
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
32
33
#include <stdio.h>
 
#define asize(arr) (sizeof arr / sizeof arr[0])
 
enum color {
    RED,
    BLUE,
    GREEN
};
 
struct item {
    int val;
    enum color clr;
};
 
int main(void)
{
    struct item cont[] = {
        { 123, RED },
        { 456, BLUE },
        { 789, RED },
        { 15, GREEN },
        { 100, RED },
        { 55, BLUE }
    };
    struct item *p;
    int i;
    
    for (i = 0, p = cont; i < asize(cont); i++, p++)
        if (p->clr == RED)
            printf("%d: %d\n", i + 1, p->val);
    return 0;
}
Код
[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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.06.2013, 23:00
Помогаю со студенческими работами здесь

Какой язык лучше / прибыльнее?
И так, мне 16 лет, седня днем пойду подавать документы в техникум на программиста соответственно. И...

Какой язык веб-программирования выбрать? Плюсы\минусы
Вопрос что ни на есть из раздела священных, но все же... Какой язык веб-программирования кто...

Какой язык лучше изучать с нуля?
Привет Всем!! Ребята подскажите пожалуйста какой язык лучше изучать с нуля ????? За ответ заранее...

Какой язык лучше изучать C или C++
Всем здравствуйте! Я новичок в программировании(знаю только Паскаль). Сейчас выбираю, какой язык...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
140
Закрытая тема Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru