Kto napisze najbardziej wydajny kod - ten wygrywa

Odpowiedz Nowy wątek
2017-10-09 20:10
2

Na codility jest test demo: https://codility.com/demo/take-sample-test/?skip_intro=1


Treść zadania:

Funkcja/metoda otrzymuje tablicę A jako argument. Zmień ją tak by wyrzucała najmniejszą liczbę całkowitą, większą od 0, której nie ma w tablicy A.
Tablica A może mieć od 1 do 1 000 000 elementów, a każdy element jest z przedziału od -100 000 do 100 000.
np. int A[] = {3, 6, 7, 3, -1, 1, -2} wynik: 2.


.

Ja za performance takiego czegoś dostałem 75%: (prawie 0(n)).

// you can also use imports, for example:
 import java.util.*;
import java.util.stream.Collectors;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
 
class Solution {
    public int solution(int[] A) {
        Set<Integer> a = Arrays.stream(A).filter(x -> x > 0).boxed().collect(Collectors.toSet());
 
        int aSize = a.size();
 
        for(int i =1; i <= aSize && i <= 100000; i++){
            if(!a.contains(i)){
                return i; 
            }
        }
        return aSize +1;
    }
}

Na Codewars można czytać rozwiązania innych a tutaj nie ma, a chętnie bym się dowiedział jak to zrobić lepiej.

edytowany 14x, ostatnio: Julian_, 2017-10-10 17:58
Pokaż pozostałe 7 komentarzy
Przetłumaczyłem temat na język polski. - somekind 2017-10-10 17:33
@somekind: i zgubiłeś jego sens... poprawię... - Julian_ 2017-10-10 17:58
Nie można zgubić czegoś, czego nie ma. :P - somekind 2017-10-10 18:12
Uwaga: treść tego posta różni się od treści zadania na Codility. W Codility wartości są większe od liczby elementów. - vpiotr 2017-10-14 08:27
co do wydajności to trzeba jeszcze zauważyć, że złożoność algorytmiczna wcale nie musi oznaczać, że coś się będzie szybciej lub wolniej wykonywać. - LukeJL 2017-10-14 11:43

Pozostało 580 znaków

2017-10-09 20:27
5

Nudzę się to masz:

fn solution(arr: &[i64]) -> usize {
  let mut tab = [false; 100_000];
 
  for &i in arr {
    if i > 0 {
      tab[i - 1 as usize] = true;
    }
  }
 
  tab
    .iter()
    .enumerate()
    .find(|&(_, &val)| !val)
    .map(|(idx, _)| idx + 1)
    .unwrap_or(1)
}

I tutaj złożoność jest liniowa.

Wersja w Javie:

class Solution {
    public int solution(int[] A) {
        bool[] res = new bool[100000];
 
        for (int i: A) if (i > 0) res[i - 1] = true;
 
        return IntStream.range(0, res.length)
            .filter(x -> res[x])
            .findFirst()
            // .map(x -> x + 1) - WTF Java?
            // .orElse(1);
            .orElse(0) + 1;
    }
}

Coś takiego, ale nie za bardzo znam Javę (BTW co to za absurd, że w Javie nie ma find* które przyjmuje predykat O.o)


Tutaj źle zrozumiałem zadanie

# Ruby

def solution(array)
  max = array.max
 
  if max < 0 then 0 else max + 1 end
end

# Elixir

defmodule Solution do
  def solution(list), do: list |> Enum.max(fn -> 0 end) |> clamp()
 
  defp clamp(n) when n < 0, do: 0
  defp clamp(n), do: n + 1
end

# Rust

fn solution(arr: &[i64]) -> u64 {
  arr.iter().max().map(|n| if n < 0 { 0 } else { n + 1 }).unwrap_or(0)
}

# Erlang

solution(List) :- clamp(list:max(List)).
 
clamp(N) when N < 0 :- 0;
clamp(N) :- N + 1.

Chyba już widzisz najlepsze rozwiązanie? Wszystko w O(n).

edytowany 14x, ostatnio: hauleth, 2017-10-11 14:27
Pokaż pozostałe 3 komentarze
Co tam robisz to się domyślam, ale jak na Javę to jak przetłumaczyć ten Twój find i map? - Julian_ 2017-10-09 20:54
@Julian_: dodałem wersję w Javie, i stwierdzam, że ten język jest conajmniej "dziwny". - hauleth 2017-10-09 21:20
. Co do Elixira - Enum.max/2 jako drugi parametr przyjmuje funkcję, więc musisz dać fn -> 0 end. Co do Erlanga- kropkę dajesz tylko na końcu funkcji, a klauzule oddzielasz średnikami. I oczywiście zmienne z Wielkiej litery ;) Szkoda, że nie są to poprawne rozwiązania, ale szacun za bycie poliglotą. - Pipes 2017-10-10 22:10
@Pipes: nie za często używam Enum.max/2 bo jak musze to w 99.9% przypadków liczę to po stronie DB, bo szybciej, zwłaszcza jak masz btree index. A co do Erlanga, to nie za dużo w nim piszę, ale masz rację. Już poprawiłem. - hauleth 2017-10-11 14:29
Ja też nie ;) Głównie piszę w Elixirze, ale Erlanga znam... (trudno nie znać w takim wypadku). Sam też z Enum.max/2 rzadko korzystam, bo jakoś nie mam takich use caseów :D - Pipes 2017-10-12 08:30

Pozostało 580 znaków

2017-10-09 21:09
3

Napisałem w C#, ale podobno to podróbka Javy, więc powinieneś zrozumieć. Wykorzystałem tablicę wartości typu bool - jeśli liczba występuje w tablicy A, to w elemencie tablicy B o indeksie tej liczby pomniejszonej o jeden zapisuję wartość true, a na końcu odnajduję pierwszy element z wartością false i szukana liczba jest indeksem tego elementu powiększonym o jeden. Dla ułatwienia można by było zdefiniować tablicę o ilości elementów większej o jeden, wtedy nie trzeba by było dodawać i odejmować jeden od indeksu.

class Solution 
{
    public int solution(int[] A) 
    {
        bool[] B = new bool[1000000];
        for (int i = 0; i < A.Length; i++)
            if (A[i] > 0)
                B[A[i] - 1] = true;
        for (int i = 0; i < 1000000; i++)
            if (B[i] == false)
                return i + 1;
        return 0;
    }
}
Pokaż pozostałe 8 komentarzy
co to znaczy wszystkie tutoriale? ;) - Julian_ 2017-10-09 21:32
Do każdej lekcji jest PDF z teorią na temat wydajności (reading material). - Burmistrz 2017-10-09 21:34
ale jakiej lekcji, że kurs jakiś na codility? - Julian_ 2017-10-09 21:35
Popatrz na linki "Lessons" i "Challenges" w górnej części strony. - Burmistrz 2017-10-09 21:36
o, super sprawa... - Julian_ 2017-10-09 21:38

Pozostało 580 znaków

2017-10-09 21:34
cmd
1
def minint(A):
    B = [i for i in range(1, max(A) + 2)]
    for i in B:
        if i not in A:
            return i
 
edytowany 2x, ostatnio: cmd, 2017-10-09 22:22
Pokaż pozostałe 3 komentarze
Po aktualizacji nadal masz O(n^2). Podpowiedź to operator in (not in A). Dodatkowo Co gdy dane wejściowe to same liczby ujemne? Zwróci None. Dodatkowo max(A) + 2) a nie max(A) + 1) - anonimowy 2017-10-09 22:17
@anonimowy fakt dla tych ujemnych trochę przypał, nawet tego nie przetestowałem ;D - cmd 2017-10-09 22:21
Wystarczy, że dodasz return 1 po pętli. I po co robisz listę z generatora a potem i tak po tym iterujesz tak jak iterowałbyś po generatorze? - anonimowy 2017-10-09 22:22
Nie będę już edytował, niech pozostanie jako pomnik mojej hańby, ale z in ciągle nie wiem o co chodzi. Patrze właśnie do docs pythona i in ma time complexity O(n) - cmd 2017-10-09 22:27
Dokładnie. A wykonujesz go co chwilę przy każdej iteracji w tablicy B. Ja np. skorzystałem z set, który dla in ma complexity O(1) - anonimowy 2017-10-09 22:29

Pozostało 580 znaków

2017-10-09 21:36
2

O ile się nie mylę to jest O(n) ? Performance dostałem 100%

class Solution {
    public int solution(int[] A) {
        boolean existingValues[] = new boolean[1000000];
 
        for (int tabElement : A) {
            if (tabElement > 0) {
                existingValues[tabElement - 1] = true;
            }
        }
 
        for (int i = 0; i < existingValues.length; i++) {
            if (!existingValues[i]) {
                return i + 1;
            }
        }
        return 0;
    }
}
Tak, masz O(n). - hauleth 2017-10-09 21:42
@hauleth: jak to liczysz? Bo ja zawsze chciałem się nauczyć ale jakoś zawsze się mylę w tym :( - Dregorio 2017-10-12 11:27
@Dregorio: w głowie. Masz 2 pętle, z których każda wykonuje n operacji, czyli czas wykonania całości to 2n co daje nam O(n). W niektórych przypadkach czasami bywa ukryty koszt jak in w Pythonie czy w Elixirze (które są liniowe względem rozmiaru tablicy lub logarytmiczne w przypadku zbiorów, bo muszą znaleźć czy element występuje, dostęp do bidi tablicy jest w czasie stałym). - hauleth 2017-10-12 12:52

Pozostało 580 znaków

2017-10-09 21:56
2

Nauczyliście mnie, teraz taka muzyka:


i wchodzi R:

solution <- function(A, maxElementsInA = 1000000){
  t <- logical(maxElementsInA)
  for(i in sort(A)){
    t[i] <- i > 0
  }
  which.min(t)
}
edytowany 1x, ostatnio: Julian_, 2017-10-09 21:57

Pozostało 580 znaków

2017-10-09 22:00
3
Julian_ napisał(a):

Nauczyliście mnie, teraz taka muzyka

Słyszę tam moją ulubioną nutę Cis (C#).

zaraz sprawdzimy, tylko nuty znajdę... - Julian_ 2017-10-09 22:01
pudło! :D nie ma Cis przy kluczu. Pierwsze Cis pojawia się dopiero w 74 takcie, ale to tylko brzmi jak Cis, a tak na prawdę to jest Des. - Julian_ 2017-10-09 22:06
Ok, może mi się wydawało, brzmiało podobnie https://www.youtube.com/watch?v=_Ljbw-UpHjw. Żartuję, nie znam się na muzyce i strzelałem... - Burmistrz 2017-10-09 22:09

Pozostało 580 znaków

2017-10-09 22:12
4

Wrzucam trochę lepsze rozwiązanie w Pythonie. Nie dość, że czytelniejsze to mniejsza złożoność.

def solution(A):
    A = set(A)
    for i in range(1, 1000001):
        if i not in A:
            return i
Pokaż pozostałe 9 komentarzy
Spójrz jeszcze raz na tamto rozwiązanie. Tam odwolujesz się do konkretnych wartości, a nie szukasz po tablicy. - wartek01 2017-10-13 16:35
@wartek01: a ja miałem namyśli to rozwiązanie pythonowe. To na nie odpowiadałem. - anonimowy 2017-10-13 17:21
@anonimowy: moje rozwiązanie jest szybsze, dla procesora niż Twoje, bo "ukryte koszty" są mniejsze (nie jest potrzebne generowanie hasha). - hauleth 2017-10-13 18:55
w realnej sytuacji trzeba by było zrobić benchmarki co się opłaca w danej sytuacji, gdzie często wirtualna maszyna na której stoi dany język (i to, jak bardzo zopymalizowane są pewne elementy języka) ma duże znaczenie. - LukeJL 2017-10-14 11:46
w tym rozwiązaniu wszystko rozbija się o to, jak konstruowany jest set. nie znam pythona na tyle, żeby stwierdzić czy to, że znana jest liczba elementów oraz że są one intami ma znaczenie, niech ktoś kompetentny się wypowie :) w zależności od tego, czy zbudowanie takiego seta ma O większe od O(n) to to rozwiązanie będzie równe lub gorsze od tablicowego - wartek01 2017-10-14 16:02

Pozostało 580 znaków

2017-10-09 22:18
0
anonimowy napisał(a):

Wrzucam trochę lepsze rozwiązanie w Pythonie. Nie dość, że czytelniejsze to mniejsza złożoność.

def solution(A):
    A = set(A)
    for i in range(1, 1000001):
        if i not in A:
            return i

R też tak umie:

solution <- function(A, maxElement = 100000){
  x <- 1:maxElements 
   for(i in x){
    if(!(i %in% A)){
      return (i)
    }
  }
}

ale czy to na pewno mniejsza złożoność obliczeniowa?

edytowany 1x, ostatnio: Julian_, 2017-10-09 22:19

Pozostało 580 znaków

2017-10-10 16:06
0

Rozwiązanie Pythonowe przedstawione przez @anonimowy dostanie 100% for sure.


Wiedza to potęga

Pozostało 580 znaków

2017-10-10 19:39
1

cpp jeszcze nie było, tak na szybko

#include <algorithm>
 
int solution(vector<int> &A) {
    std::vector<bool> found(1000000, false);
 
    for(const auto number : A)
    {
        if(number > 0)
        {
            found[number] = true;
        }
    }
 
    const auto findBeginIt = std::next(std::cbegin(found));
    const auto falseIt = std::find(findBeginIt, std::cend(found), false);
    return static_cast<int>(std::distance(std::cbegin(found), falseIt));
Użył bym std::array zamiast std::vector jako, że rozmiar znamy już w czasie kompilacji. - hauleth 2017-10-11 14:30
nie byłem pewny czy się zmieści na stosie - stryku 2017-10-11 18:12
@stryku: w Ruscie się zmieściło, to w C++ też się zmieści. - hauleth 2017-10-12 12:53

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę