Есть ли смысл использовать собственные реализации базовых АТД в C++?

#cpp #алгоритм #типы_данных #функциональное_программирование #стандарт

Задался вопросом, имеет ли смысл в настоящее время использовать собственные реализации
таких типов данных как связный список/стек/очередь/словарь? Именно для выполнения реальных
задач, а не в учебных целях. Казалось бы, стандарт языка С++ на данный момент предоставляет
большое количество инструментов, но несмотря на это, в некоторых проектах всё ещё продолжают
использовать самописные реализации тех или иных АТД. В том редком случае, когда стандартные
средства уступают в производительности самописным, логично, что выбор вряд ли будет
в пользу стандартных. Но в большинстве случаев нет какой-либо критичной разницы между
двумя подходами. Так стоит ли игра свеч?
    

Ответы

Ответ 1

Реализация контейнеров и алгоритмов в STL или Boost - веселая штука. Их делают максимально
унифицированными (в основном для покрытия максимального кол-ва задач) и очень тщательно
проверяют на быстродействие и т.д.
Их пишут не один десяток людей, а ревьювят его вообще все ). Это дает гарантию что
конкретная реализация будет максимально удовлетворять потребностям большинства.
Время когда люди писали свои "общие" контейнера и алгоритмы наверное прошло. Но во
в задачах (пример: Вам нужен произвольный доступ, и ассоциотивность) - да надо писать
свой костыль.
В стандартах очень много ассемблерных вставок для оптимизации производительности,
и поэтому я не думаю что компилятор родит более вменяемый код, чем тот над которым
посидели оптимизаторы.


ИМХО: В реальных задачах надо брать готовое, а не рожать что-то (ибо дорого) сейчас
вообще большинство ничего не кодит (дешевле найти готовое и пришить), что разумеется
пичалька

Как создать словарь по типу X:X*X от 1 до n, используя map()

#python #map #dict #функциональное_программирование

Как создать словарь по типу X:X*X длиной от 1 до n c Map. Должно получиться:

{1: 1,
 2: 4,
 3: 9,
 4: 16,
 5: 25,
 6: 36,
 7: 49,
 8: 64,
 9: 81,
 10: 100,
 11: 121,
 12: 144,
 13: 169,
 14: 196,
 15: 225,
 16: 256,
 17: 289,
 18: 324,
 19: 361,
 20: 400}




numbers=[]
for x in range(1,6):
  numbers = map(lambda x: x**2, range(1,10))
print(numbers)

    

Ответы

Ответ 1

In [71]: n = 10

In [72]: d = dict(map(lambda x: (x,x**2), range(1, n+1)))

In [73]: d
Out[73]: {1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81, 10: 100}


PS но использование map в данном случае, по-моему, извращение



Если бы не условие использовать map() я бы делал это так:

In [76]: d = {i:i**2 for i in range(1, n+1)}

In [77]: d
Out[77]: {1: 1, 2: 4, 3: 9, 4: 16, 5: 25, 6: 36, 7: 49, 8: 64, 9: 81, 10: 100}


выглядит гораздо понятнее...

Как получить каждый n-ый элемент из списка с помощью Stream API?

#java #java_8 #java_stream #функциональное_программирование

Предположим, у меня есть такой список:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


Можно ли использовать Java Stream API для переноса каждого второго элемента из этого
списка, чтобы получить такой список?

[1, 3, 5, 7, 9]


Или, может быть, каждый третий элемент?

[1, 4, 7, 10]


По сути, я ищу такую функцию, чтобы взять каждый n-ый элемент из потока:

List list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
List list2 = list.stream().takenth(3).collect(Collectors.toList());
System.out.println(list2);
// => [1, 4, 7, 10]

    

Ответы

Ответ 1

Одним из главных мотивов для введения потоков Java было разрешение параллельных операций.
Это привело к требованию, чтобы операции Java Streams, такие как map и filter, не зависели
от положения элемента в потоке или элементов вокруг него. У этого есть преимущество,
оно позволяет легко разделять потоки для параллельной обработки. Недостатком является
сложность некоторых операций.

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

Самый простой способ выполнить ваше требование - использовать индекс списка:

List list = ...;
return IntStream.range(0, list.size())
    .filter(n -> n % 3 == 0) //3 - каждый 3-ий элемент
    .mapToObj(list::get)
    .collect(Collectors.toList());


Примечание от Sergey Gornostaev:


  Решение рабочее, но должен заметить, подобное применение стримов - это
  антипаттерн. Не желательно работать с данными за пределами стрима. Как
  только появляется идея об обращении к переменной, стоит насторожиться
  и подумать "Я использую стримы неправильно или стримы тут вообще не
  подходят?"




Используя Stream.iterate 

List list = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

int skip = 3;
int size = list.size();
// Limit to carefully avoid IndexOutOfBoundsException
int limit = size / skip + Math.min(size % skip, 1);

List result = Stream.iterate(0, i -> i + skip)
    .limit(limit)
    .map(list::get)
    .collect(Collectors.toList());

System.out.println(result); // [1, 4, 7, 10]




Используя библиотеку Guava(GitHub):

Streams
    .mapWithIndex(stream, SimpleImmutableEntry::new)
    .filter(entry -> entry.getValue() % 3 == 0)
    .map(Entry::getKey)
    .collect(Collectors.toList());




Используя библиотеку AbacusUtil:

Stream.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
        .filter(MutableInt.of(0), (e, idx) -> idx.getAndDecrement() % 3 == 0)
        .println();




Используя библиотеку jOOλ и ее метод zipWithIndex():

System.out.println(
Seq.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
   .zipWithIndex()             // This produces a Tuple2(yourvalue, index)
   .filter(t -> t.v2 % 3 == 0) // Filter by the index
   .map(t -> t.v1)             // Remove the index again
   .toList()
);

Что в коде противоречит парадигме функционального программирования?

#python_3x #функциональное_программирование

На вход подаются две последовательности (a₁,…,an) и (b₁,…,bn) из 0 и 1.

Вычислите последовательность из (c₁,…,cn), где каждая cᵢ=xor(aᵢ,bᵢ).

import sys


def xor(a, b):
    return ((not a) * b) + (a * (not b))


print(
    *map(
        xor,
        map(
            int,
            sys.stdin.readline().split()
        ),
        map(
            int,
            sys.stdin.readline().split()
        )
    )
)


проверочная система отвечает: Precompile check failed: not functional enough
    

Ответы

Ответ 1

Помогла замена Функции 

def xor(a, b):
    return ((not a) * b) + (a * (not b))


на lambda

lambda a, b: ((not a) * b) + (a * (not b))

Реализация чисел Фибоначчи с помощью хвостовой рекурсии в Haskell

#функции #рекурсия #haskell #функциональное_программирование

Решаю задачу с рядом фибоначчи (+ отрицательные). Приблизительно так:

fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n | n == 0 = 1
                 | n > 0 = fibonacci (n - 1) + fibonacci (n - 2)
                 | n < 0 = fibonacci (n + 2) - fibonacci (n + 1)


нужно увеличить скорость просчета. для этого естественно нужен аккумулятор.

Как это сделать?
    

Ответы

Ответ 1

Правильнее всего, конечно, использовать готовую формулу n-ого члена :) Но для случая,
когда нужно находить программным путём, подходит следующая идея (пишу алгоритм, не
знаю синтаксис Хаскеля):

fib n = helper 0 1 n
  where helper curr prev n
          | n == 0   = curr
          | n > 0    = helper (curr+prev) curr (n-1)
          | n < 0    = helper prev (curr-prev) (n+1)


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

Неверный порядок выполнения алгоритма на Python в функциональной парадигме

#python #python_3x #функции #функциональное_программирование

Нужно решить задачу полностью в функциональном стиле, т.е. в одну строку, без циклов
(совсем нельзя использовать for) и без присваиваний.

Задача требует сначала ввести число n, затем вводится n последовательностей. К ним
нужно применить функцию zip (дальше не важно, к вопросу не относится). Написал такой код:

print(*zip(map(lambda x: list(map(int, input().split())), range(int(input())))))


До применения zip всё правильно, но в zip, кажется, последовательности передаются
по одной, так что, на практике выходит так:

Ввод:

2
0 0
1 1


Правильный вывод:

(0, 1) (0, 1)


Действительный вывод:

([0, 0],) ([1, 1],)


Как сделать правильно, и чтобы при этом оставаться в функциональной парадигме?
    

Ответы

Ответ 1

Добавив к вашему решению одну звездочку можно получить необходимый результат:

print(*zip(*map(lambda x: list(map(int, input().split())), range(int(input())))))
#          ^  <--- NOTE


вывод:

(0, 1) (0, 1)


пояснение на примере:

In [159]: list(zip([[0, 0], [1,1]]))
Out[159]: [([0, 0],), ([1, 1],)]          #  то что получилось

In [160]: list(zip([0, 0], [1,1]))
Out[160]: [(0, 1), (0, 1)]                #  то что нужно получить

In [161]: list(zip(*[[0, 0], [1,1]]))     # решение
Out[161]: [(0, 1), (0, 1)]


PS Что значит * (звёздочка) и ** двойная звёздочка в Питоне?




Функция zip(*iterables) принимает ноль и более позиционных аргументов и разница в
вызове zip(lst) и zip(*lst) в том как будут обрабатываться переданные аргументы:


при вызове: zip(lst) - передается один аргумент типа list
при вызове: zip(*lst) - передается все содержимое списка как отдельные позиционные
аргументы


Пример с функцией print():

In [105]: lst = [1,2,3]

In [106]: print(lst)
[1, 2, 3]

In [107]: print(*lst)
1 2 3


тот же результат мы получим передав три раздельных параметра:

In [108]: print(1,2,3)
1 2 3

Что такое функциональное программирование?

#функции #функциональное_программирование

Часто противопоставляют функциональный подход и ООП. Не совсем понятно, почему? Что
отличает функционально программирование? Лямбды и наличие функций типа map, fold, reduce
и т.д.?

Update:
В чем заключается функциональный подход с точки зрения практики?
    

Ответы

Ответ 1

Функциональное программирование - способ организации вычислений без состояния. Строго
говоря, состояние у такой программы конечно есть, это - совокупность контекстов всех
её функций. Но: главная проблема, стоящая за сложностями состояния, идентичности и
изменения, состоит в том, что, введя присваивание, мы вынуждены внести в свои вычислительные
модели понятие времени (time). До того, как появилось присваивание, наши программы
от времени не зависели — в том смысле, что всякое выражение, обладающее значением,
всегда имело одно и то же значение. 

На практике, используя ФП вы идёте от простого к сложному: организуете зависимости,
отношения, преобразования и композиции функций. Способы делать это - суть методологии
ФП. Функции ваши восновном "чисты", не мутируют внешнего контекста, а их результат
зависит только от переданных параметров. ФП полностью избавляет от возможности совершения
целого класса ошибок (cм.  SICP Х. Абельсон, Д. Д. Сассман: гл. "Ловушки императивного
программирования"). 

Неверно считать, что в функциональном стиле можно писать только на языке сверхвысокого
уровня с искусственным интеллектом вместо компилятора. Разумеется, это можно делать
на любом языке программирования, в котором есть функции высшего порядка. Более того,
механика функций - основа любого интерпретатора и эта механика довольно проста, а вот
введение самого понятия переменных и их мутации сильно усложняет устройство интерпретатора. 

ФП противопоставляют ООП восновном потому, что в обратную сторону пошла волна хайпа,
созданная в своё время вокруг Java и C++. Оказалось, что библиотеки шаблонов и многоуровневые
иерархии объектов не решили всех проблем, даже наоборот, создав новые. По-прежнему
бесконтрольно возрастает сложность программных систем, а соответственно и их стоимость.
Тут мы наблюдаем рациональное обращение отрасли к фундаментальным основам, имеющее
целью уменьшить энтропию.


Ответ 2

В императивном подходе (а ООП может быть им, и обычно им и является), программист
расписывает, как именно нужно исполнять его программу.

В функциональном подходе программист пишет "что нужно сделать", а вот как это делать,
решает компилятор или транслятор.

Всякие лямбды, map/reduce ещё не делают программирование функциональным. 

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

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


Ответ 3

В противопоставлении ООП и функционального, проблему сужают до противопоставления
того кем манипулирует, либо функциями, либо изменяемыми объектами. Но это слишком узкий
взгляд: объектами могут быть функции и функции могут хранить значения. Императивное
программирование стало популярно из-за относительно простой трансляции таких программ
на популярные процессорные архитектуры, на которых программы, в функциональном стиле,
особо выдающихся результатов не демонстрируют, т.е. более сложная и более продолжительная
трансляция функциональных программ дает код несколько худшего качества на них. Но программы
на изменяемых состояниях(объектах) невозможно смасштабировать, если заранее не внести
дополнительные механизмы распределения нагрузки ( по ядрам, компьютерам, сетям ), разделения
ресурсов ( файлов, общих зон памяти ) и взаимной коммуникации для получения результатов
работы. Вопрос в другом — может ли функциональное программирование упростить решения
этого вороха проблем?! И да, и нет. Высокоуровневое функциональное SQL представление
помогает распределять нагрузку на реляционные базы, но об линейном росте от количества
ядер(компьютеров) речь не идет. Высокий уровень OpenGL позволяет писать программы выполняющие
гигантские объемы вычислений, даже в императивных языках(так он был создан), распределяя
нагрузку на GPU ядрах. Но нехватка ресурсов была и остается узким местом любой программы,
для любой операционной системы. А коммуникации — к решению этих проблем только подходят,
и императивные языки пытаются решать их в функциональном стиле, полностью отказавшись
от управления в «ручном» стиле «состояний».

Что в коде противоречит парадигме функционального программирования?

На вход подаются две последовательности (a₁,…,an) и (b₁,…,bn) из 0 и 1.
Вычислите последовательность из (c₁,…,cn), где каждая cᵢ=xor(aᵢ,bᵢ).
import sys
def xor(a, b): return ((not a) * b) + (a * (not b))
print( *map( xor, map( int, sys.stdin.readline().split() ), map( int, sys.stdin.readline().split() ) ) )
проверочная система отвечает: Precompile check failed: not functional enough

Ответ

Помогла замена Функции
def xor(a, b): return ((not a) * b) + (a * (not b))
на lambda
lambda a, b: ((not a) * b) + (a * (not b))

Неверный порядок выполнения алгоритма на Python в функциональной парадигме

Нужно решить задачу полностью в функциональном стиле, т.е. в одну строку, без циклов (совсем нельзя использовать for) и без присваиваний.
Задача требует сначала ввести число n, затем вводится n последовательностей. К ним нужно применить функцию zip (дальше не важно, к вопросу не относится). Написал такой код:
print(*zip(map(lambda x: list(map(int, input().split())), range(int(input())))))
До применения zip всё правильно, но в zip, кажется, последовательности передаются по одной, так что, на практике выходит так:
Ввод:
2 0 0 1 1
Правильный вывод:
(0, 1) (0, 1)
Действительный вывод:
([0, 0],) ([1, 1],)
Как сделать правильно, и чтобы при этом оставаться в функциональной парадигме?

Ответ

Добавив к вашему решению одну звездочку можно получить необходимый результат:
print(*zip(*map(lambda x: list(map(int, input().split())), range(int(input()))))) # ^ <--- NOTE
вывод:
(0, 1) (0, 1)
пояснение на примере:
In [159]: list(zip([[0, 0], [1,1]])) Out[159]: [([0, 0],), ([1, 1],)] # то что получилось
In [160]: list(zip([0, 0], [1,1])) Out[160]: [(0, 1), (0, 1)] # то что нужно получить
In [161]: list(zip(*[[0, 0], [1,1]])) # решение Out[161]: [(0, 1), (0, 1)]
PS Что значит * (звёздочка) и ** двойная звёздочка в Питоне?

Функция zip(*iterables) принимает ноль и более позиционных аргументов и разница в вызове zip(lst) и zip(*lst) в том как будут обрабатываться переданные аргументы:
при вызове: zip(lst) - передается один аргумент типа list при вызове: zip(*lst) - передается все содержимое списка как отдельные позиционные аргументы
Пример с функцией print()
In [105]: lst = [1,2,3]
In [106]: print(lst) [1, 2, 3]
In [107]: print(*lst) 1 2 3
тот же результат мы получим передав три раздельных параметра:
In [108]: print(1,2,3) 1 2 3