Какой язык программирования лучше? (2) - Священные войны - Страница 7

@Igor3D · 17.06.2013, 16:35

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

Сообщение от Убежденный

Реализация на чистом C++11 :

Ответ кодом часто лучший, но здесь форыч не в масть, речь идет о быстром поиске, а не линейном переборе

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

Давайте

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

Какой угодно, используйте любые средства Вашего языка, сторонние либы тоже можно. Цвет - ну хотя бы uint32. Что-то долго раскачиваетесь

@nullxdth · 17.06.2013, 17:14

Сообщение от 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) достаточно "быстрый" поиск?

@korvin_ · 17.06.2013, 17:16

А если так

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)

?

Убежденный · 17.06.2013, 17:16

Сообщение от 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

Да, и я по-прежнему жду эквивалентной реализации на С.

@Igor3D · 17.06.2013, 17:21

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

Просто LOL. Возьмём хеш-таблицу с ключами по цветам.

Не сачкуйте. Дан исходный контейнер, нужны хеш-таблицы - делайте их (а не "возьмем"). И реультат печатайте. Совсем распустились на "прогрессивных" языках.

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

Жду код на Си (ясный и прекрасный код) с бОльшей

или такой же эффективностью.

Поверьте, эффективность там намного больше, а про расход памяти/ресурсов и говорить неудобно

Но сначала намекну: Вы решаете задачу "найти все с данным цветом". Это не совсем то что сказано в условии - и это маленькое отличие многое меняет.

@nullxdth · 17.06.2013, 17:22

Сообщение от 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.

@korvin_ · 17.06.2013, 17:25

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

По plist'у поиск линейный.

А, точно, ну да ладно.

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

Не сачкуйте. Дан исходный контейнер

Ты же сам сказал, что «любой», я вот сразу прикинул и решил изначально хранить в хеш-таблице. =)

@nullxdth · 17.06.2013, 17:26

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

Не сачкуйте. Дан исходный контейнер, нужны хеш-таблицы - делайте их (а не "возьмем").

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

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

Я чего-то упустил?

Мне было предложено выбрать любой контейнер, я взял хеш-таблицу? ЧЯДНТ?

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

И реультат печатайте.

Блин, улыбнуло.

@korvin_ · 17.06.2013, 17:27

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

Но сначала намекну: Вы решаете задачу "найти все с данным цветом". Это не совсем то что сказано в условии - и это маленькое отличие многое меняет.

Ну так надо как-то сразу выбирать подходящий контейнер, обычно ж так делают, не?

@nullxdth · 17.06.2013, 17:28

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

Поверьте, эффективность там намного больше, а про расход памяти/ресурсов и говорить неудобно

Хех, ты просто жжёшь

В некой реализации на Си временная эффективность поиска лучше чем O(1).
Я хочу это видеть! Код в студию

@korvin_ · 17.06.2013, 17:28

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

Поверьте, эффективность там намного больше

Прям таки намного? Быстрее, чем O(1)? Не, допустим хеш-функция в CL не так быстро сумму считает, но уж прям чтобы намного, как-то не верится.

@nullxdth · 17.06.2013, 17:42

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

Но сначала намекну: Вы решаете задачу "найти все с данным цветом". Это не совсем то что сказано в условии - и это маленькое отличие многое меняет.

Задача решена полностью в соответствии с условием.

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

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

Задача решена полностью в соответствии с условием.

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

Lisp
1
'(:a . :red)

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

@Igor3D · 17.06.2013, 17:50

Сообщение от Убежденный

Да нет проблем:

Вполне нормальное решение на плюсах, но все-таки 2 двоичных поиска, а можно обойтись вообще без поисков. Также механизм не очень общий - напр может быть не разрешено менять порядок элементов в исходном контейнере (пусть это др задача - но все же). Тогда создавать/таскать доп. ассоциативный контейнер накладно.

Не спешите, подумайте. Свою версию выложу завтра

@taras atavin · 17.06.2013, 17:54

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

Вполне нормальное решение на плюсах, но все-таки 2 двоичных поиска, а можно обойтись вообще без поисков.

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

@nullxdth · 17.06.2013, 18:34

Чтобы не потерять взаимосвязь между названиями и цветами, можно задать элементы как 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)

А также, никакой реализации на Си мы пока не увидели

Убежденный · 17.06.2013, 18:38

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

Дан исходный контейнер, нужны хеш-таблицы - делайте их (а не "возьмем").

Зачем делать готовое ?
Язык предоставляет реализации, значит логично использовать их, если только нет
каких-то совершенно исключительных противопоказаний. Я таких противопоказаний пока
не встречал. Свою реализацию красно-черного или AVL-дерева писать не вижу смысла:
вопрос обогнать (думаю, что ближе к истине - не догнать) Dinkumware/STLPort не стоит,
тем более, что скорость работы программ в большей степени упирается в правильную
алгоритмизацию, а не в детали ее имплементации.

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

Поверьте, эффективность там намного больше, а про расход памяти/ресурсов и говорить неудобно

А обосновать ? Забыли ?

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

Вы решаете задачу "найти все с данным цветом". Это не совсем то что сказано в условии - и это маленькое отличие многое меняет.

На всякий случай выделил жирным:

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

Есть массив/контейнер элементов, каждый из которых имеет цвет (color). Надо быстро найти все с тем же цветом что и данный элемент

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

Вполне нормальное решение на плюсах, но все-таки 2 двоичных поиска

Согласен, быстрее было бы multiset::equal_range.

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

а можно обойтись вообще без поисков.

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

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

Также механизм не очень общий - напр может быть не разрешено менять порядок элементов в исходном контейнере

Этого не было в условии задачи.
Контейнер не сортирован - линейный поиск. Сортирован - двоичный. Оба варианта были приведены,
оба наглядны, переносимы и опираются исключительно на стандартные средства языка.
Ваш ход.

@Igor3D · 17.06.2013, 19:05

Сообщение от Убежденный

Зачем делать готовое ?
Язык предоставляет реализации, значит логично использовать их, если только нет
каких-то совершенно исключительных противопоказаний. Я таких противопоказаний пока
не встречал.

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

Сообщение от Убежденный

Свою реализацию красно-черного или AVL-дерева писать не вижу смысла:
вопрос обогнать (думаю, что ближе к истине - не догнать) Dinkumware/STLPort не стоит,
тем более, что скорость работы программ в большей степени упирается в правильную
алгоритмизацию, а не в детали ее имплементации.

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

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

А также, никакой реализации на Си мы пока не увидели

Шо за нетерплячка?

Сказал же - завтра, даю время подумать и применить все "самое прогрессивное".

Убежденный · 17.06.2013, 19:24

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

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

"Есть массив/контейнер элементов, каждый из которых имеет цвет".

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

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

Сказал же - завтра, даю время подумать и применить все "самое прогрессивное".

Ваше решение настолько прогрессивное, что его нельзя написать за 5 минут ?

accept · 17.06.2013, 20:44

Сообщение от Убежденный

Хочу увидеть эквивалентный код на 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;
}

Code
1
2
3
4
5
6
[guest@localhost cont]$ .ansi t.c -o t
[guest@localhost cont]$ ./t
1: 123
3: 789
5: 100
[guest@localhost cont]$

@megaromul · 17.06.2013, 23:00

за Delphi где голосуют?

Новые блоги и статьи Все статьи Все блоги /
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .

@megaromul 0 / 0 / 0 Регистрация: 04.04.2013 Сообщений: 14
	17.06.2013, 23:00
	за Delphi где голосуют? 0