Kto napisze najbardziej wydajny kod - ten wygrywa

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.

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).

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;
    }
}
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

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;
    }
}
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)
}
3
Julian_ napisał(a):

Nauczyliście mnie, teraz taka muzyka

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

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
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?

0

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

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));
1

A take coś :

function solution(arr)
   {
       var B = new Array(100000);
       for(var i = 0; i < 1000000; i++) 
       {
           if(arr[i] > 0)
           {
              B[arr[i]] = false;
           }
       }  

       for(var i = 0; i < 100000; i++) 
       {
           if(B[i] == false)
           {
              return i - 1;
           }
       } 
    }
1

Ta je lepsza kod:

function solution(A)
   {
       
       var B = [];
       for(var i = 0; i < 1000000; i++) 
       {
           if(A[i] > 0 !in_array)
           {
              B.push(A[i]);
           }
       }

       B.sort(function(a,b) { return a - b; }); 

       
      
       if(B.lenght !== 0)
       {

		   for(var i = 0; i < 100000; i++) 
		   {
		       if(((B[i] + 1) !== B[i + 1]) && (B[i] !== B[i+1]))
		       {
		          return B[i]+1;
		       }
		   } 

           
       }
       else
       {
          return 1;
       }
    }

44%

1

Siem pomylila

B.length

Tera dali 55%

2

js:

function solution(A) {
    const setA = new Set(A);
    
    for (let i = 1; i <= A.length + 1; i++) {
        if (!setA.has(i)) {
            return i;
        }
    }
}
13
create function solution(in int[]) returns bigint as
$$
select min(lp) from (select el, row_number() over(order by el) lp from unnest($1)  x(el) where el>0) x where el<>lp
$$ language sql

:)

0

Javascript:

function solution(A) {
    const filtered = new Set(A.filter(item => item > 0));
    if(!filtered.size) return 1;
    let result = null, iterator = 1;
    const size = filtered.size + 1;
    while(iterator <= size){
        if(!filtered.has(iterator)) return iterator;
        iterator++;
    }
}
1

Przykładowe rozwiązanie w Elixirze:

defmodule Solution do
  def find_min_positive_not_in_the_list(list) do
    list
    |> Enum.filter(&Kernel.>(&1, 0))
    |> find_min_positive_not_in_the_filtered_list()
  end

  defp find_min_positive_not_in_the_filtered_list([]), do: 1
  defp find_min_positive_not_in_the_filtered_list([h | t]) do
    if h + 1 not in t do
      h + 1 
    else
      find_min_positive_not_in_the_filtered_list(t)
    end
  end
end

Dla przykładowej listy:

a = [3, 6, 7, 3, -1, 1, -2]
Solution.find_min_positive_not_in_the_list(a) # 2

Warto zwrócić uwagę na treść zadania, że ma zwracać najmniejszą liczbę całkowitą większą od 0 czyli 1 lub większą.

0

Tutaj moje rozwiązanie, bazuje na pozbyciu się testu czy liczba jest ujemna:

int main()
{
	int A[] = { 3, 6, 7, 3, -1, 1, -2, 0, 34753745 };
	unsigned int *B = (unsigned int *)A;
	register unsigned int lowest = B[0];

	for (int i = 1; i < 9; ++i)
	{
		if (B[i] < lowest && B[i] > 1)
		{
			lowest = B[i];
		}
	}

	printf("lowest = %d", (int)lowest - 1);
	return (int)lowest - 1;
}
5

pierwsze podejście - 15 minut robienia i... 0 procent, bo miałem błąd off-by-one. Właczyłem od nowa, zamieniłem zero na jedynkę, po czym... miałem 11 procent, bo znowu coś wyskoczyło (jakiś prosty warunek brzegowy), więc go szybko uzupełniłem i wrzuciłem taki kod (jedna z wczesnych wersji):

function solution(A) {
    let result;
    if (!A.includes(1)) return 1;
    for (let i = 0; i < A.length; i++) {
        const c = A[i] + 1;
        if (!A.includes(c)) result = c;
    }

    if (result < 0) result = 1;
    return result;
    
}

dostałem 44 punkty i
Detected time complexity: O(N**2)
no i w pewnych innych warunkach brzegowych podawał inny wynik (correctness 80%, performance 0%).
przy okazji poprawiania warunku brzegowego (około 30 sekund mi zajęło poprawianie tego warunku), wpadłem na pomysł, żeby zmienić trochę algorytm i sortować tablicę

Wysmarowałem więc inne rozwiązanie od zera (przez 6 minut), ale coś fejlowało, bo znowu warunek brzegowy, wziąłem jakąś prostą poprawkę (znowu z 30 sekund) i coś nie działało, kolejną poprawkę (kolejne 30 sekund) i znowu. Potem dwie minuty znowu modyfikacja rozwiązania i znowu coś fejluje.
...
No i po iluś takich próbach - pokombinuj coś przez minutę, submituj, zobacz wyniki - zmodyfikuj algorytm - w końcu udało mi się osiągnąć 100 na 100.
screenshot-20171014103747.png

i kodzik

function solution(A) {
    A = A.filter(a => a >= 0).sort((a,b)=>a-b);
    
    for (let i = -1; i < A.length; i++) {
        const curr = i > -1? A[i] : 0;
        if (curr < 0) continue;        
        const next = A[i + 1], candidate = curr + 1;
        if (curr != next && next != candidate)
           return candidate;
    }   
}

Detected time complexity:
O(N) or O(N * log(N))

Jakie wnioski?

  • jestem pewnie słabym algorytmiarzem(tj. słabym olimpijczykiem, maturzystą, uczestnikiem hackatonu itp.) - nie umiałem napisać czegoś poprawnie za pierwszym razem, a potem nie przewidziałem przypadków brzegowych. Gdyby to był test do firmy to odpadłbym w przedbiegach (moja pierwsza próba nawet nie działała poprawnie!). Jakbym miał brać udział w olimpiadzie matematycznej czy hackatonie też bym przegrał.
  • jednak jako developer wykazałem się jednak ogarnięciem i sprytem - wykorzystałem logi o błędach do poprawienia algorytmu, i w skutek tego osiągnąłem w końcu maksymalny wynik. Potrafiłem też szybko myśleć, skoro na sygnał "wywala się" potrafiłem szybko zmodyfikować algorytm, żeby kolejnymi krokami przybliżać się do postawionego sobie celu. Dostrzegam również wady ostatecznego rozwiązania, które nie zostały wykryte przez maszynę (np. nie podoba mi się, że filtruję i sortuję tablicę na wejściu, mam wrażenie, że to może być nie do końca wydajne).

Tylko, że tak - w realnej pracy programisty, wymagane są raczej te drugie skille - nikt nie każe zrobić czegoś w chwilę, tylko raczej ma się więcej czasu, kombinuje, poprawia się, żeby osiągnąć dobre rozwiązanie. A ten test mierzy to pierwsze, czyli umiejętność klepania algorytmów na czas.

Więc samo zadanie ciekawe, ale sam sposób działania Codility pozostawia wiele do życzenia (zwróćcie uwagę, że mogłem kilka razy podchodzić tylko dlatego, że była to wersja demo - więc wchodziłem jeszcze raz w całość. W zadaniu do pracy bym miał tylko jedno podejście i rosyjska ruletka - albo zadziała - albo nie). Czyli Codility mierzy umiejętność niepopełniania pomyłek, a niekoniecznie umiejętność myślenia.

1 użytkowników online, w tym zalogowanych: 0, gości: 1