All streams
Search
Write a publication
Pull to refresh
3
Karma
0
Global rating
@Inspector-Due

User

Send message
ProfileArticlesPostsNewsComments43
Как задачи на LeetCode прокачали меня как разработчика, или по-честному про алгоритмы
Java

image

This comment wasn’t rated yet0
Look
Как задачи на LeetCode прокачали меня как разработчика, или по-честному про алгоритмы

Более того, у Scala как-то странно считается время исполнения! 700 мс на очень маленьком тесте. (Ну и Scala 3 нет)


Картинка

image


Но вообще очень жаль, что Haskell нет на большинстве подобных площадок. А если и есть (например, CodeForces или sort-me), то либо старая версия GHC (8.10.7), либо даже нет самых базовых вещей по типу vector (приходится юзать array, а тут уже не получится воспользоваться AoS/SoA). С другой стороны CF и sort-me про спортивное программирование (бег в мешках?), а Haskell, как показывает практика, слабо для этого подходит.

This comment wasn’t rated yet0
Look
Telegram клиент. TDLib и Spring Boot

Кстати, а существуют ли клиенты на Java, которые напрямую общаются через MTProto? Например, как pyrogram или telethon? Я пытался что-то такое найти, но нашёл лишь какую-то очень старую библиотеку с устаревшим layer (62, емнип).

Total votes 1: ↑1 and ↓0+1
Look
Микросервисы — отчуждение от результатов труда
К слову о ChatGPT

Похоже, она подходит лишь для того, чтобы эссе написать, а так она выдаёт такое:

А также, захотев разобраться с тем, что такое Post's lattice, я получил "also known as the Post canonical system..."

В общем, пора перебираться в математики, чтобы нейросеть не могла заменить меня (любителя перекладывать джейсончики и байтики)

This comment wasn’t rated yet0
Look
Столлман извинился за свое поведение, и его не исключили из FSF
Мне никто не посылает невербальные сигналы, никто не клеит на улицах, никто не раздевается рядом в кустиках…

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

Наверное, нет такого человека, у которого бы не было потребности в тесном общении. Но создаётся такое впечатление, что то самое тесное общение вам не особо-то и нужно. Но раз вы упоминаете самооценку, значит, вы всё же задумываетесь об этом?
Я всё же верю в то, что почти на каждого человека найдётся другой человек.
убейте меня
И не забывайте, что есть люди, которым кажется, что вы интересный человек (хотя, по комментариям на хабре, наверное, не очень хорошо судить, ведь по большей части здесь обсуждаются какие-то вещи, связанные с информационными технологиями, так что это то, о чём вы написали во втором абзаце).
наверное, я выбрал неправильное место для комментария
This comment wasn’t rated yet0
Look
Go против Rust — производительность вне конкуренции

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

  1. Тот же вариант, что и описан в оригинальной статье. type SickTriplet = [3]float64

  2. Вариант, использующий type Triplet struct { a, b, c float64 }, но создающий новую копию при каждой итерации

  3. То же, что и (2), но только данные мутируются на месте.

Код
package triplet 

import (
	"math/rand"
	"math"
)

type SickTriplet = [3]float64

func randomSickTriplet() *SickTriplet {
	return &SickTriplet{rand.Float64(), rand.Float64(), rand.Float64()}
}

func getNextSickTriplet(trip *SickTriplet) *SickTriplet {
	app := trip[0] + trip[1] - trip[2]
	if math.Abs(app) <= 1.0 {
		return &SickTriplet{trip[1], trip[2], app}
	} else {
		return &SickTriplet{trip[1], trip[2], 1.0 / app}
	}
}

func calcSickTriplet(trip *SickTriplet, num int) *SickTriplet {
	for i := 0; i < num; i++ {
		trip = getNextSickTriplet(trip)
	}
	return trip
}

func fastCalcSickTriplet(trip *SickTriplet, num int) *SickTriplet {
	for i := 0; i < num; i++ {
		app := trip[0] + trip[1] - trip[2]
		trip[0] = trip[1]
		trip[1] = trip[2]
		if math.Abs(app) <= 1.0 {
			trip[2] = app
		} else {
			trip[2] = 1.0 / app	
		}
	}
	return trip
}

type Triplet struct { a, b, c float64 }

func randomTriplet() *Triplet {
	return &Triplet{rand.Float64(), rand.Float64(), rand.Float64()}
}

func fastCalcTriplet(trip *Triplet, num int) *Triplet {
	for i := 0; i < num; i++ {
		app := trip.a + trip.b - trip.c
		trip.a = trip.b
		trip.b = trip.c
		if math.Abs(app) <= 1.0 {
			trip.c = app
		} else {
			trip.c = 1.0 / app	
		}
	}
	return trip
}

func getNextTriplet(trip *Triplet) *Triplet {
	app := trip.a + trip.b - trip.c
	if math.Abs(app) <= 1.0 {
		return &Triplet{trip.b, trip.c, app}
	} else {
		return &Triplet{trip.b, trip.c, 1.0 / app}
	}
}


func slowCalcTriplet(trip *Triplet, num int) *Triplet {
	for i := 0; i < num; i++ {
		trip = getNextTriplet(trip)
	}
	return trip
}

Сам бенчмарк:

package triplet

import "testing"


const TIMES = 1000000


func BenchmarkFastCalcTriplet(b *testing.B) {
	for i := 0; i < b.N; i++ {
		fastCalcTriplet(randomTriplet(), TIMES)
	}
}

func BenchmarkSlowCalcTriplet(b *testing.B) {
	for i := 0; i < b.N; i++ {
		slowCalcTriplet(randomTriplet(), TIMES)
	}
}

func BenchmarkCalcSickTriplet(b *testing.B) {
	for i := 0; i < b.N; i++ {
		calcSickTriplet(randomSickTriplet(), TIMES)
	}
}

func BenchmarkFastCalcSickTriplet(b *testing.B) {
	for i := 0; i < b.N; i++ {
		fastCalcSickTriplet(randomSickTriplet(), TIMES)
	}
}

Результаты такие:

BenchmarkFastCalcTriplet-4       	     548	   2177936 ns/op	      24 B/op	       1 allocs/op
BenchmarkSlowCalcTriplet-4       	      62	  18613275 ns/op	24000044 B/op	 1000001 allocs/op
BenchmarkCalcSickTriplet-4       	      62	  18929575 ns/op	24000036 B/op	 1000001 allocs/op
BenchmarkFastCalcSickTriplet-4   	     534	   2225462 ns/op	      24 B/op	       1 allocs/op

Получается, выбор структуры данных не особо и влияет?

This comment wasn’t rated yet0
Look
Go против Rust — производительность вне конкуренции

(А также @PsyHaSTe) Так, ну, я немного покопался в коде и вот что понял:

data Triplet = Triplet !Double !Double !Double deriving Show

getNextTriplet :: Triplet -> Triplet
getNextTriplet (Triplet a b c)
  | abs app <= 1.0 = Triplet b c app
  | otherwise = Triplet b c (1.0 / app)
  where
    app = a + b - c

iterateOver' :: Triplet -> Int -> Triplet
iterateOver' trip n = foldl' (\t _ -> getNextTriplet t) trip [1..n]

Наверняка тут можно уйти в unboxed types...

Примечание

В оригинальном коде, конечно, чуть сложнее (если текущий и следующий Triplets очень схожи, то об этом будет написано в консоли и всё (то есть можно брать iterateOver' и не париться):

(~=) :: Double -> Double -> Bool
a ~= b = abs (a - b) < 1e-14

isConvergent :: Triplet -> Triplet -> Bool
isConvergent (Triplet a b c) (Triplet x y z)
  = (a ~= x) && (b ~= y) && (c ~= z)

iterateOver :: Triplet -> Int -> (Triplet, Maybe (Int, Double))
iterateOver triplet cycles
  = foldl' f (triplet, Nothing) [1..cycles]
  where
    f (trip, r) n = (nextTrip, nextR)
      where
        nextTrip = getNextTriplet trip
        Triplet a b c = nextTrip
        nextR = if isConvergent trip nextTrip then r <|> Just (n, b) else r

Далее поговорим про конкурентность. Вообще там много кода, направленного на создание собственного бенчмарка. Суть в следующем: есть series_size, который характеризует, как много таких вот iterateOver' будет запущенно параллельно. Далее для каждого r \in [1; \text{tasks_max}]делаем следующее: запускаем \lceil \frac{r}{\text{series_size}}\rceilраз в series_size параллельных потоков iterateOver' с рандомно сгенерированным Triplet и фиксированным n. Ну и собираем какие-то метрики, которые агрегируем и выводим на экран.

Кстати, в коде, судя по всему, есть логическая ошибка. Допустим, tasks_max = 10, а series_size = 3. Тогда для r = 1 лишь один раз запустится iterateOver', хотя мы, вроде как, тестируем конкурентность и iterateOver' должен конкурентно запуститься вseries_size = 3 потоках. Ну, так же и для всех r, не кратных series_size.

Пояснение к предыдущему абзацу

Перепишем вот этот код так, чтобы он просто печатал нам, какая task в какой серии запускается.

Получится

package main

import "fmt"

func count_series(n_tasks, series_size int) int {
	n_series := n_tasks / series_size

	if series_size*n_series < n_tasks {
		n_series++
	}

	return n_series
}

func main() {
	n_tasks := 10
	series_size := 3
	n_series := count_series(n_tasks, series_size)
	task_idx := 0

	for series_idx := 0; series_idx < n_series; series_idx++ {
		count_tasks_series := 0
		for task_idx < n_tasks && count_tasks_series < series_size {
			fmt.Printf("Running task # %d in series # %d\n", task_idx, series_idx)
			count_tasks_series++
			task_idx++
		}
	}
}

Ну и что мы получим?

Running task # 0 in series # 0
Running task # 1 in series # 0
Running task # 2 in series # 0
Running task # 3 in series # 1
Running task # 4 in series # 1
Running task # 5 in series # 1
Running task # 6 in series # 2
Running task # 7 in series # 2
Running task # 8 in series # 2
Running task # 9 in series # 3

То есть таски 0..2, 3..5, 6..8 реально запускаются по-нормальному так, что параллельно будут выполняться ровно три (series_size) функции. А вот таска # 9 будет выполняться одна. Очевидно, одна параллельная задача выполнится быстрее трёх параллельных, так что это будет влиять на результаты бенчмарка.

Да и в чём смысл сравнивать горутины с каким-то там crossbeam в Rust, я не знаю. Ведь горутины нужны не для того, чтобы дробить числа, а для IO.

Total votes 7: ↑7 and ↓0+7
Look
Есть ли жизнь без тестов?

С отрицанием, конечно, ситуация становится много интереснее, но я не могу понять, как можно сконстуировать тип Either a (a -> Void)? Это же закон исключённого третьего, с которым в интуиционистской логике, есть какие-то подоводные камни. И ещё: как, например, считать данные откуда-то, если, например, у value p тип не условныйInt, а непосредственно само число? То есть надо грязное значение из IO представить в виде чистого типа.

This comment wasn’t rated yet0
Look
Есть ли жизнь без тестов?

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

Давайте на примере! Допустим, у нас есть банк, но у нас есть система отслеживания подозрительных платежей. Так вот платёж считается подозрительным, если платеж превышает 100'000 у.е. И/ИЛИ тот, кто отправлял деньги, совершил за день платежей на 1'000'000 у.е. Такие платежи должны проходить ручную модерацию, соответственно, нам их надо замечать. Допустим, программист устал, вчера вечером и ночью в клубе был, сегодня на работе у него завал был, а эту часть кода писал сильно вечером, потому что сроки горят. Программист написал "(ЭтотПлатёж > 100'000) ИЛИ/И (Сумма(Платежи, ЭтотДень) > 1'000'000)" (в общем, перепутал И и ИЛИ. Требованием было написать И, он написал ИЛИ, или, наоборот, просили ИЛИ, а он написал И)

Как защититься от таких ошибок?

Я предложу своё решение на Haskell для случая, когда просили И, а программист написал ИЛИ.

Решение!

Очевидно, в силу вступает произведение типов (для продвинутых можно было бы, наверное, пойти в уровень kinds, но и моя реализация, на мой взгляд, спасает от ошибок). Для лучшего эффекта надо вынести некоторые конструкторы в отдельный файл и не экспоритровать их, чтобы не допустить ошибки (случайно не создать их). Извините за длинные названия и за ужасное качество кода, но думаю, что я смог минизировать ошибку перепутать И с ИЛИ. Кстати, заметьте, здесь нет ни &&, ни ||!

Вот возникает вопрос по поводу второго случая (когда надо ИЛИ, а программист пишет по ошибке И). Это можно реализовать, использовав тип-сумму, но у меня вопрос: допустим, нам надо отправить пользователю причину, по которой его платёж оказался на ручной модерации. Если платёж превышает 100'000, то причина "платёж превышает 100'000". Если сумма за день больше 1'000'000, то причина "сумма за день больше 1'000'000". А если и то, и другое, то "платёж превышает 100'000" и "сумма за день больше 1'000'000". Вот как это изящно отразить последний случай в системе типов? Не писать же data Reason = A | B | A_And_B?

module Main where

import Text.Read ( readMaybe )
import System.Environment ( getArgs )

main :: IO ()
main = do
  args <- getArgs
  case parseArgs args of
      Just (aop, somftd) -> 
          case isUserSuspicious aop somftd of
            Just _ -> putStrLn "The user is suspicious"
            Nothing -> putStrLn "The user is NOT suspicious"
      Nothing -> putStrLn "Usage: ./program <amount of payment> <sum of money for this day>"

parseArgs :: [String] -> Maybe (AmountOfPayment, SumOfMoneyForThisDay)
parseArgs [aop, somftd] = (,) <$> (AmountOfPayment <$> readMaybe aop) <*> (SumOfMoneyForThisDay <$> readMaybe somftd)
parseArgs _ = Nothing


newtype AmountOfPayment = AmountOfPayment Int deriving (Eq, Show)

newtype SumOfMoneyForThisDay = SumOfMoneyForThisDay Int deriving (Eq, Show)

-- The constructor should be hidden
data ThisPaymentIsSuspicious = ThisPaymentIsSuspicious deriving (Eq, Show)

isThisPaymentSuspicious :: AmountOfPayment -> Maybe ThisPaymentIsSuspicious
isThisPaymentSuspicious (AmountOfPayment x)
  | x > 100000 = Just ThisPaymentIsSuspicious
  | otherwise = Nothing

-- The constructor should be hidden
data SumOfMoneyForThisDayIsSuspicious = SumOfMoneyForThisDayIsSuspicious deriving (Eq, Show)

isSumOfMoneyForThisDaySuspicious :: SumOfMoneyForThisDay -> Maybe SumOfMoneyForThisDayIsSuspicious
isSumOfMoneyForThisDaySuspicious (SumOfMoneyForThisDay x)
  | x > 1000000 = Just SumOfMoneyForThisDayIsSuspicious
  | otherwise = Nothing


data TheUserIsSuspicious = TheUserIsSuspicious ThisPaymentIsSuspicious SumOfMoneyForThisDayIsSuspicious deriving (Eq, Show)

isUserSuspicious :: AmountOfPayment -> SumOfMoneyForThisDay -> Maybe TheUserIsSuspicious
isUserSuspicious aop somftd = TheUserIsSuspicious <$> isThisPaymentSuspicious aop <*> isSumOfMoneyForThisDaySuspicious somftd

This comment wasn’t rated yet0
Look
Драма об одарённых детях, или Откуда растут ноги у выгорания молодых кадров

Ещё можно отметить соревновательный момент в так называемых надстройках над системой образования: олимпиады, экзамены, специальные классы, целые школы и ВУЗы для талантливых детей создают нездоровую образовательную атмосферу, в которой на раз-два вылетаешь из заведения (из дверей, из окна — как получится).

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

Total votes 6: ↑6 and ↓0+6
Look
[Личный опыт] Жизнь в Швеции: полное благополучие, тесты на IQ и тысячи вакансий в IT
Ответ (возможно, неправильный)

τ₁ → τ₂

Забавно, что примерно то же самое можно отразить в Haskell (или это самообман?) (это ведь обычный curry):

rule :: ((γ, τ₁) -> τ₂) -> (γ -> (τ₁ -> τ₂))
rule f = \g -> \x -> f (g, x)

У меня вопрос по поводу нотации: можно ли вот ту запись, которую вы написали, воспринимать как "если Γ, x : τ₁ ⊢ ε : τ₂, то Γ ⊢ λx:τ₁. ε : τ₁ → τ₂"?

И можно ли аналогичное применить для ⊢? Ну, то есть выражение "Γ, x : τ₁ ⊢ ε : τ₂" читать как "из Γ, x : τ₁ следует ε : τ₂"? Я вообще электрик, но интересно, как это читать.

This comment wasn’t rated yet0
Look
Как не разочароваться в программировании и не отчислиться после второго курса

Немного сна

А не страдает ли от этого всё остальное (т.е. "пары, прорешивание задавальника в общаге, самообразование в программировании")?

This comment wasn’t rated yet0
Look
Удивительное приключение в стране оптимизирующих компиляторов

Если я ничего не попутал, то вот мои результаты:

Первая версия (до `n / 2`):

C++ (clang): 0.295 с

C++ (gcc): 0.938 с

GHC (llvm): 0.521 с

GHC: 1.138 с

Вторая версия (до корня):

C++ (clang): 2.397 с

C++ (gcc): 6.784 с

GHC (llvm): 3.526 с

GHC: 8.408 с

Тесты запускал пару раз, брал минимальный результат (хотя, во всех тестах разница во времени была минимальна)

Тут только один вывод: используйте GHC с LLVM!

И один вопрос! Как там получилось, что у меня версия на clang быстрее, чем на GHC?

На всякий случай покажу код и команды, которые были во время теста, может, я что-то недоглядел.

Hidden text

Для C++:

#include <iostream>
#include <vector>

using std::vector;

template <typename integer>
integer isqrt(integer x) {
    integer q = 1;
    while (q <= x)
        q <<= 2;
    integer r = 0;
    while (q > 1) {
        q >>= 2;
        integer t = x - r - q;
        r >>= 1;
        if (t >= 0) {
            x = t;
            r += q;
        }
    }
    return r;
}

static bool is_prime(const long n, const vector<long> &P) {
  long l = isqrt<long>(n);
  for (auto p : P) {
    if (p > l) return true;
    if (!(n % p)) return false;
  }
  return true;
}

int main(int argc, char *argv[]) {
  if (argc < 2) {
    std::cerr << "Specify limit" << std::endl;
    return 1;
  }

  const unsigned long limit = std::stol(argv[1]);

  vector<long> primes = {2};

  for(long n = 3; n <= limit; n += 2) {
    if (is_prime(n, primes)) {
      primes.push_back(n);
    }
  }

  std::cout << primes.size() << std::endl;

  return 0;
}

Команда, которой компилировал: clang++ primes.cpp -O3 -o primes-clang++

Результат выполнения: time ./primes-clang++ 25000000

1565927

real	0m2.394s
user	0m2.391s
sys	0m0.004s

Теперь Haskell

{-# OPTIONS_GHC -O2 -fllvm #-}

module Main where

import System.Environment

primes :: Int -> [Int]
primes n = ps
  where
    ps = 2 : [ n | n <- [3, 5 .. n], isPrime n ]
    isPrime n = all (\p -> n `rem` p /= 0) $ takeWhile (<= (floor $ sqrt $ fromIntegral n)) ps

main :: IO ()
main = do
  [cnt] <- getArgs
  print $ length $ primes $ read cnt

Команда, которой компилировал: ghc WithLLVM.hs

Время выполнения: time ./WithLLVM 25000000

1565927

real	0m3.520s
user	0m3.476s
sys	0m0.044s

Я думаю, что это у меня проблема во время компиляции хаскельного кода:

[1 of 1] Compiling Main             ( WithLLVM.hs, WithLLVM.o )
You are using an unsupported version of LLVM!
Currently only 9 to 13 is supported. System LLVM version: 13.0.1
We will try though...
Linking WithLLVM ...

Почему-то 13.0.1 уже не нравится :(

GHC версии 8.10.7 (хотя, это особо не влияет. На новом 9.2.2 такой же результат)

This comment wasn’t rated yet0
Look
Илон Маск предложил создать соцсеть «без пропаганды»

Извините за оффтоп, но почему вам выгодно, чтобы писало больше людей на хаскеле? Или это пример не имеющий с реальностью ничего общего?

This comment wasn’t rated yet0
Look
Бесплатные инстансы в облаках — это ловушка

А у орскл его ещё можно получить на каком нибудь "бесплатном обучении" без привязки карты

Я правильно понимаю, что информацию об этому можно найти здесь: https://education.oracle.com/learning-explorer ?

This comment wasn’t rated yet0
Look
Калькулятор на типах TypeScript
Total votes 3: ↑3 and ↓0+3
Look
Разработчики YouTube Vanced объявили о прекращении развития проекта

Можно же поправить вручную, потом написать программу, который бы автоматически правил определённую версию. Наверное, это и имелось в виду под "внедрялкой".

Total votes 1: ↑1 and ↓0+1
Look
Я разработал генератор ASCII-арта в Node JS

Я попытался измерить "яркость" каждого символа, но у меня получилась другая последовательность @MBW0Q8#O$&UqpbdmXa%kZhwoI[]unC}1{YJftzxjLvcl?|<>i)(/+!*r;~^":,-_'`

Как я измерял: брал каждый символ, рисовал его, далее переводил в grayscale, далее суммировал значение всех пикселей. Чем больше — тем ярче и наоборот. Я думаю, проблема в том, что я как-то неправильно рисую. Или, может быть, что все эти символы подбирались эмпирическим путём.

Вот результаты эксперимента: https://imgur.com/a/Ue8HEuB

Первый скриншот — "палитра" этой статьи, а второй — моя "палитра"

Total votes 1: ↑1 and ↓0+1
Look
Я разработал генератор ASCII-арта в Node JS

Это делается, когда происходит конвертация из RGB в grayscale.

Конкретно в той библиотеке это сделано таким образом. На SO есть объяснение

This comment wasn’t rated yet0
Look
arr[-1] или самые редкие конструкции в С

Забавная ситуация, кстати

#include <stdio.h>
#include <stdint.h>

int main(void) {
    int a, b;
    int *p = &a + 1;
    int *q = &b;
    printf("%p %p %d %d\n", (void *)p, (void *)q, p == q, (uintptr_t) p == (uintptr_t) q);
    return 0;
}

Компилировал с флагом -O2, вывод: 0x... 0x... 0 1

Может быть, стоит использовать uintptr_t, чтобы написать функцию doesOverlap?

This comment wasn’t rated yet0
Look
BackHere
1
23

Information

Rating
Does not participate
Registered
Activity

Your account

Sections

Information

Services

Support
© 2006–2025, Habr