Программирование без использования условных конструкций

@Olejan_one · Регистрация: 25.08.2012

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

Ребят, задали на собеседовании такую задачку:
Есть метод с тремя параметрами - bool flag, del1 a,del1 b.
Необходимо реализовать этот метод так, что бы в зависимости от флага вызывался нужный делегат.
Все ничего, вот только надо сделать так, что бы в реализации не было логических операций(if,else,case...).
Была подсказка использовать hash-совместимые контейнеры типа dictionary. Но я так и не придумал верного решения.
Может кто знает как это должно выглядеть?
Спасибо.

@kolorotur · 27.11.2016, 14:57

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

Может кто знает как это должно выглядеть?

Примерно так:

C#
1
2
3
4
5
6
7
8
var actions = new Dictionary<bool, del1>
{
   [false] = a,
   [true]  = b
};
 
bool flag = ...;
actions[flag]();

@Пaтрик · 27.11.2016, 14:57

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
using System;
using System.Collections.Generic;
using System.Reflection;
 
namespace Thread1861494
{
    internal class Program
    {
        private static readonly Dictionary<bool, Action<int, int>> Handlers;
 
        private static void Action1(int a, int b)
        {
            Console.WriteLine(MethodInfo.GetCurrentMethod().Name);
        }
 
        private static void Action2(int a, int b)
        {
            Console.WriteLine(MethodInfo.GetCurrentMethod().Name);
        }
 
        static Program()
        {
            Handlers = new Dictionary<bool, Action<int, int>>
            {
                { false, Action1 },
                { true, Action2 }
            };
        }
 
        private static void Foo(bool f, int a, int b)
        {
            Handlers[f](a, b);
        }
 
        private static void Main(string[] args)
        {
            Foo(false, 1, 2);
            Foo(true, 1, 2);
            Console.ReadLine();
        }
    }
}

@Olejan_one · 27.11.2016, 15:17 **[ТС]**

Ох, спасибо ребят, все оказывается намного легче чем я думал. Просто никогда с дикшенари не работал еще. Еще небольшой вопросик по поводу хештейбл и дикшенари. Где можно почитать удобную информацию о этих коллекциях? В гугле искал, но то что нашел не очень воспринимается. Может есть книги, где доступно описано хеширование и использование этих коллекций? Спасибо.

@aquaMakc · 28.11.2016, 10:45

Olejan_one, в принципе, если без использования if`ов, то можно было и так сделать:

C#
1
(flag ? a : b)();

Само-собой, если целью задания было выяснить умеет ли новобранец пользоваться словарями, этот способ не проканает.

@Usaga · 28.11.2016, 10:48

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

Просто никогда с дикшенари не работал еще.

Если ты с коллекциями толком работать не умеешь, то про собеседования думать рановато.

@aquaMakc · 28.11.2016, 10:50

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

Где можно почитать удобную информацию о этих коллекциях?

Например, тут

@Olejan_one · 28.11.2016, 15:17 **[ТС]**

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

Например, тут

Спасибо, статью прочитал. Неплохо написано, но всё же мне все равно не очень ясно несколько вещей:
1. Собственно, насколько я понял суть хешей в контексте коллекций состоит в том, что можно быстро найти нужный элемент. Мне не очень ясен сам алгоритм поиска -
Поправьте меня если не правильно описываю:
а) Класс, который реализует ключи должен переопределять метод GetHashCode().
б) Соответственно получается что например при поиске ключа "Саша" словарь хеширует строку "Саша" и получает хеш, к примеру 122345.
в) дальше начинается перечисление ключей и вызов метода GetHashCode() на каждом элементе для сравнения с хешем 122345?

По моему результат будет долгим.
Или я что то не так понял.

2. Мне не понятно что такое "емкость словаря или Capacity". Я привык к свойству Count. Соответственно сколько элементов добавилось, такая и емкость коллекции. Добавилось 5 элементов - коллекция динамически возрастает на это количество. А что такое емкость словаря не пойму, и почему она может отличаться от количества элементов, которые находятся в словаре.

3. В случае возникновения коллизии есть 2 метода реализации:
а) Метод линейного поиска - объекты, ключи которых образуют одинаковый хеш преобразуются в линейный односвязный список, каждый элемент в котором содержит адрес следующего элемента в списке. У меня вопрос - у нас есть значение "Маша", образующее хеш 65478. В словаре есть еще 50 элементов, которые возвращают такой же как и у "Маши" хеш - 65478. Соответственно у нас по значению хеша 65478 - появляется линейный список из 51 элемента. Как в этом случае происходит поиск по этому линейному списку? Как нам найти значение "Маша"? На этом этапе словарь использует уже не значение хеша а сам ключ "Маша" и сравнивает его с каждым ключом списка?

б) Метод открытой адресации: тут почти все понятно. Элементы с одинаковым хешем помещаются не в список, а друг за другом по словарю, в первую пустую позицию после элемента с которым совпал хеш. Вопрос: в каждой статье пишут, что в этом случае элементы должны распределяться равномерно по словарю. Это как? Допустим есть элемент "Саша" с хешем 45678 и элемент "Маша" с таким же хешем 45678. В итоге мы вставляем Сашу в ячейку под номером 45678. Далее следующая ячейка под номером 45679 уже занята другим элементом. В итоге Машу мы вставляем в следующую свободную ячейку - к примеру 45680.
Что в итоге получилось:
45678 - Саша
45679 - Коля
45680 - Маша

В чем заключается равномерность данного словаря?

Спасибо. Буду благодарен за любой ответ.

@aquaMakc · 28.11.2016, 15:29

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

По моему результат будет долгим.

я внутрь исходников мелкософта не лазил и точно ответить не смогу. Подозреваю, что именно так и происходит. Не думаю, что человеческими органами чувств будет замечен спад производительности, но использовать в качестве ключа тип String я бы вообще не рекомендовал.

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

А что такое емкость словаря не пойму

Грубо-говоря - объём памяти, зарезервированный под словарь, при добавлении элемента свыше этого количества происходит пересоздание коллекции, с соответствующими накладными расходами.

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

В случае возникновения коллизии есть 2 метода реализации

Вот тут не подскажу. Ищи и разбирай исходники.

@Olejan_one · 28.11.2016, 15:51 **[ТС]**

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

Грубо-говоря - объём памяти, зарезервированный под словарь, при добавлении элемента свыше этого количества происходит пересоздание коллекции, с соответствующими накладными расходами.

Ага, ну так уже яснее. Но все же я ж не буду каждый раз вычислять обьем данных, он может каждый раз быть разным. Наверно это хорошо когда размер данных близок к постоянному. Т.е. когда я заранее могу его знать примерно. Ну да ладно, разберусь с этим. Спасибо большое.

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

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

1
(flag ? a : b)();

Тернарный оператор - это условная конструкция. А надо без неё. Ну варианты уже есть, и этого хватило. Dictionary решает задачу.

@aquaMakc · 28.11.2016, 15:52

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

Тернарный оператор - это условная конструкция. А надо без неё.

Я сначала прочитал задачу как "...без использования if..."

@kolorotur · 28.11.2016, 17:50

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

Класс, который реализует ключи должен переопределять метод GetHashCode().

Не только.
Так же он должен переопределить Equals и желательно (но не обязательно) реализовать интерфейс IEquatable.
Потому что если два объекта равны через метод Equals, то они должны генерировать и одинаковый хэш.

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

в) дальше начинается перечисление ключей и вызов метода GetHashCode() на каждом элементе для сравнения с хешем 122345?

Нет.
Словарь группирует все добавляемые значения по их хэшу. Когда вы делаете поиск, то высчитывается хэш только того ключа, который вы передали для поиска — чтобы определить группу, в которой должно находиться искомое значение. Дальше идет линейный поиск по всем элементам в этой группе.

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

Мне не понятно что такое "емкость словаря или Capacity".

Емкость — это количество элементов, которое может быть добавлено в коллекцию до того, как она заполнится и придется выделять память под новые элементы.

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

сколько элементов добавилось, такая и емкость коллекции. Добавилось 5 элементов - коллекция динамически возрастает на это количество.

И с добавлением каждого элемента вам придется копировать все уже до этого добавленные для того, чтобы увеличить размер.
Это будет очень накладно и медленно — попробуйте для развлечения реализовать свой динамический массив MyList<T> с предложенным вами механизмом.
Чтобы не копировать весь массив при каждом добавлении, динамические коллекции, которые в качестве детали реализации используют обычный массив, выделяют память с запасом. Count показывает 5 элементов, а массив в кишках коллекции выделен на 8 элементов — это и есть Capacity.

Вот вам код для демонстрации:

C#
1
2
3
4
5
6
var list = new List<int>();
for (int i = 0; i < 100; i++)
{
   list.Add(i);
   Console.WriteLine($"Count = {list.Count}; Capacity = {list.Capacity}");
}

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

Как в этом случае происходит поиск по этому линейному списку?

Последовательно, вызывая Equals на каждом элементе до тех пор, пока один из них не вернет true.
Тот, который вернет, и будет считаться найденным элементом.

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

В чем заключается равномерность данного словаря?

Данного — ни в чем, потому что равномерности там нет

"Равномерность" — это, грубо говоря, разбиение массива на промежутки, где каждый промежуток назначается определенному хэшу: скажем, с первого по десятый элементы массива будут хранить объекты с хэшем 45678. С одиннадцатого по двадцатый — зарезервированы для элементов с хэшем 45679 и т.д.

Кстати, к слову о емкости коллекции: в приведенном примере словарь для хранения использует массив из двадцати элементов — это его емкость, а храниться в нем могут на данный момент только Саша и Маша: Count == 2.

@m0nax · 28.11.2016, 20:16

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

я внутрь исходников мелкософта не лазил и точно ответить не смогу. Подозреваю, что именно так и происходит. Не думаю, что человеческими органами чувств будет замечен спад производительности, но использовать в качестве ключа тип String я бы вообще не рекомендовал.

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

@aquaMakc · 28.11.2016, 22:56

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

даже если хранить там сотни тысяч записей поиск укладывается в несколько миллисекунд, какими там органами измерит

скорость - это хорошо, но тип String слишком большое поле для возможных ошибок оставляет, особенно, если значение вводится пользователем. Можно, конечно, использовать строковые константы в качестве ключа, но лучше всё-таки более однозначные типы применять. Вот это я хотел сказать.

@Olejan_one · 28.11.2016, 23:45 **[ТС]**

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

Нет.
Словарь группирует все добавляемые значения по их хэшу. Когда вы делаете поиск, то высчитывается хэш только того ключа, который вы передали для поиска — чтобы определить группу, в которой должно находиться искомое значение. Дальше идет линейный поиск по всем элементам в этой группе.

Здесь не очень понятно - Вы написали "что бы определить группу...". Как словарь ищет эту группу?
К примеру есть такой словарь mydictionary:
1000-Маша
1001-Саша->1001-Коля
1002-Вася
1003-Петя

1. Для того что бы найти обьект "Коля" мы берем метод - mydictionary.ContainsKey("Коля");
2. В этот момент словарь берет этот передаваемый параметр "Коля" высчитывает хеш для этого значения. Результат - 1001.
3. Затем как Вы сказали словарь должен найти группу, в которой находиться это значение. Для того что бы найти эту группу
необходимо сравнивать наш хеш 1001 с остальными ключами в словаре, правильно?
В нашем случае к примеру будет так:
a)Сравнение нашего хеша 1001 с первым элементом в словаре, который содержит значение "Маша". В этом случае ключ "Маша" возвращает хеш 1000. Хеши не равны. 1001!=1000.
б) Словарь переходит к следующему элементу. Вычисляет хеш элемента "Саша". Он будет равен 1001. Затем он сравнивает искомый хеш с текущим элементом. 1001==1001. Ага, хеш коды совпали, значит нашли нужный список. Далее с помощью метода Equals он сравнивает ключи. Но они не равны. Искомый у нас "Коля" а текущий "Саша". В итоге он начинает двигаться по линейному списку, переходя к следующему элементу, и находит ключ "Коля".

Правильно?

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

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

Чтобы не копировать весь массив при каждом добавлении, динамические коллекции, которые в качестве детали реализации используют обычный массив, выделяют память с запасом. Count показывает 5 элементов, а массив в кишках коллекции выделен на 8 элементов — это и есть Capacity.

Прикольно, я не знал=)

@kolorotur · 29.11.2016, 02:43

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

Для того что бы найти эту группу
необходимо сравнивать наш хеш 1001 с остальными ключами в словаре, правильно?

Нет конечно, иначе словарь ничем не будет отличаться от обычного массива.
На основании сгенерированного хэша словарь высчитывает место нужной корзины за О(1), безо всяких итераций.
Ну например у вас массив из n корзин. Примитивнейший способ нахождения нужной корзины — это взять сгенерированный хэш и найти остаток от деления его на количество корзин (n) — вы сразу же получите местоположение нужной корзины, без итераций.
Разумеется, такой способ может генерировать много коллизий (и генерирует, если GetHashCode плохо реализован), потому на деле там может быть довольно мохнатый матан, но суть в том, что местоположение корзины высчитывается по формуле, без обхода по всем корзинам.

@Olejan_one · 29.11.2016, 17:12 **[ТС]**

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

Нет конечно, иначе словарь ничем не будет отличаться от обычного массива.
На основании сгенерированного хэша словарь высчитывает место нужной корзины за О(1), безо всяких итераций.
Ну например у вас массив из n корзин. Примитивнейший способ нахождения нужной корзины — это взять сгенерированный хэш и найти остаток от деления его на количество корзин (n) — вы сразу же получите местоположение нужной корзины, без итераций.
Разумеется, такой способ может генерировать много коллизий (и генерирует, если GetHashCode плохо реализован), потому на деле там может быть довольно мохнатый матан, но суть в том, что местоположение корзины высчитывается по формуле, без обхода по всем корзинам.

Ок спасибо огромное, теперь мне уже более понятнее почему они быстрее. Буду пробовать их использовать!=)

@SatanaXIII · 30.11.2016, 14:58

kolorotur, поясните пожалуйста следующий момент.
Продолжая пример уважаемого Olejan_one:
В данном словаре:

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

1000-Маша
1001-Саша->1001-Коля
1002-Вася
1003-Петя

на поиски Коли словарю потребуется две итерации, да?
1) Сначала перейти к линейному массиву совпавших хэшей за одну итерацию.
2) Затем, убедившись, что в нулевом элементе массива неверное значение, начать перебирать массив дальше и во второй итерации, вызвав Equals(Коля) для уже первого элемента массива, обнаружить совпадение.

@kolorotur · 30.11.2016, 15:31

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

на поиски Коли словарю потребуется две итерации, да?

Итерации там в дело вступают только при нахождении нужной корзины, сама корзина определяется без итеративного процесса.
В конкретном примере для нахождения Коли потребуется три действия:
1. Высчитывание хэша для Коли = 1001
2. Проверка Саша.Equals(Коля) -> false
3. Проверка Коля.Equals(Коля) -> true

Получается, что если хранить в словаре объекты с одинаковыми хэшами, то сложность поиска будет как в обычном массиве: O(n).

@Serg34 · 09.12.2016, 07:37

Еще иногда проще использовать табличный метод

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

Программирование без использования условных конструкций

Решение

Решение

@Olejan_one 1 / 1 / 2 Регистрация: 25.08.2012 Сообщений: 108

	Программирование без использования условных конструкций 27.11.2016, 14:42. Показов 2860. Ответов 19 Метки нет (Все метки) Ребят, задали на собеседовании такую задачку: Есть метод с тремя параметрами - bool flag, del1 a,del1 b. Необходимо реализовать этот метод так, что бы в зависимости от флага вызывался нужный делегат. Все ничего, вот только надо сделать так, что бы в реализации не было логических операций(if,else,case...). Была подсказка использовать hash-совместимые контейнеры типа dictionary. Но я так и не придумал верного решения. Может кто знает как это должно выглядеть? Спасибо. 0

@Olejan_one 1 / 1 / 2 Регистрация: 25.08.2012 Сообщений: 108
	27.11.2016, 15:17 [ТС]
	Ох, спасибо ребят, все оказывается намного легче чем я думал. Просто никогда с дикшенари не работал еще. Еще небольшой вопросик по поводу хештейбл и дикшенари. Где можно почитать удобную информацию о этих коллекциях? В гугле искал, но то что нашел не очень воспринимается. Может есть книги, где доступно описано хеширование и использование этих коллекций? Спасибо. 0

@Serg34 100 / 100 / 33 Регистрация: 20.09.2014 Сообщений: 457 Записей в блоге: 3
	09.12.2016, 07:37
	Еще иногда проще использовать табличный метод 0