Какой язык программирования лучше? (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 где голосуют?

Новые блоги и статьи Все статьи Все блоги /
Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .	Лето уходит kumehtar 17.08.2026	Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега Maks 17.08.2026 Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .	Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .

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