Optymalizacja usunięcia liczby następującej po duplikacje

watpliwosci

2022-03-12T10:01:47+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 73

0

Napisałem algorytm i wydaje mi się, że jest za bardzo skomplikowany do tak prostego zadania. Język kotlin/java

Dla np. listy

Kopiuj

val input = mutableListOf(1, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2)

Chcialbym usunąć numery które występują po duplikatach (w tej liscie duplikatem jest liczba 2, poniewaz wystepuje wiecej niz 1 raz)

więc output powinien wygladac :

Kopiuj

val output = mutableListOf(1, 2, 4, 5, 2, 7, 2, 2)

Moje rozwiązanie:

Kopiuj

private fun main(list: MutableList<Int>): MutableList<Int> {
    val doubledIndexes = mutableSetOf<Int>()
    val listWithoutDoubled = mutableListOf<Int>()

    list.forEachIndexed { index, item ->
        if (!listWithoutDoubled.contains(item)) {
            listWithoutDoubled.add(item)
        } else {
            doubledIndexes.add(index)
            doubledIndexes.add(list.indexOf(list.find { it == item }))
        }
    }

    val sorted = doubledIndexes.sortedDescending()
    sorted.forEach {
        if (list.getOrNull(it + 1) != null) {
            list.removeAt(it + 1)
        }
    }
    return list
}

Mam 2 forEache, ze 3 listy, sortowanie ify...
Czy da się jakos prosciej ?

Althorion

2022-03-12T10:52:27+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 1620

3

Nie wiem, jak to zaprogramować w Kotlinie, ale bliskie optymalnemu pod względem złożoności obliczeniowej (można przyspieszyć o stały faktor, robiąc dwie rzeczy naraz przy tym samym przebiegu przez listę) będzie takie podejście:

Wygenerować sobie histogram zadanej listy. Szybkie zapytanie do DuckDuckGo pokazało mi https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/each-count.html
Zrobić sobie listę booli o takiej samej długości, jak wejściowa lista. Iterując po wejściowej liście, tam gdzie i-ty element będzie duplikatem (sprawdzamy w wygenerowanym wyżej histogramie), oznaczamy i+1-y element w liście booli jako false. Języki funkcyjne powinny mieć do tego jakąś ładną składnię.
Tworzymy nową listę powstałą z odfiltrowania listy wejściowej przez listę booli z drugiego punktu. Jw., języki funkcyjne powinny mieć coś ładnego do tego.

EDYCJA:
Przykładowa implementacja w Pythonie:

Kopiuj

from collections import Counter

def filtre_after_duplicate(l):
    histogram = Counter(l)
    mask = [True] + [1 == histogram[x] for x in l[:-1]]
    return [x for x, y in zip(l, mask) if y]

TEST_INPUT = [1, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2]
TEST_OUTPUT = [1, 2, 4, 5, 2, 7, 2, 2]
assert TEST_OUTPUT == filtre_after_duplicate(TEST_INPUT)

eleventeen

2022-03-12T13:33:21+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 143

0

Jak zlozonosc ma to co napisales? (i nawet to nie sortowanie najbardziej boli)

Czy na pewno chcesz modyfikowac przekazany argument zamiast tworzyc nowa liste? Owszem, ze wzgledow pamieciowych moze byc takie wymaganie, ale raczej czesciej bedzie tworzona nowa lista. A juz szczegolnie w jezykach typu kopiujemy_wszystko_i_udajemy_ze_to_jest_ok_bo_przynajmniej_na_watkach_sie_nie_wylozymy.

Co do wersji w pythonie: nie mam pojecia czy da sie napisac krocej ale da sie szybciej (2 przebiegi przez dane a nie 3) i zuzywajac mniej pamieci (mask nie jest potrzebne)

Shalom

2022-03-13T23:28:17+01:00

Rejestracja: dni
Ostatnio: dni
Lokalizacja: Space: the final frontier
Postów: 26433

2

Czy da się prościej?

Zliczasz występowanie liczb w jakimś HashMap albo nawet w gołej tablicy jeśli wiesz ze wartości w wejściowej tablicy są np. z zakresu 0..k, czyli lecisz przez tablicę i counting[tab[i]]+=1 to cię kosztuje O(n)
Robisz jedno przejście przez wejściową tablicę i sprawdzasz sobie czy counting[tab[i]] >1, znów kosztuje cię to O(n)

Ewentualnie można to trochę przyspieszyć jak w trakcie budowania tablicy zliczeń zrobisz sobie jeszcze "indeks", jakąś mapę wartość -> lista indexów gdzie występują (index[tab[i]].append(i)) bo wtedy to drugie przejście możesz zrobić już tylko po elementach dla których zliczenia są >1 i schodzisz do O(k). Czy warto to zależy od danych wejściowych i od tego jak duże jest k oraz n

WWA2025

2022-03-15T09:09:31+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 47

0

unexpected results

Zamiast skupiać się na prostocie i wydajności nalezy pochylić się nad funkcjonalnością

Kotlin
1 2 3 4 5 2 6 7 2 9 2
[1, 2, 4, 5, 2, 7, 2, 2] o.k.
C++
1 2 3 4 5 2 6 7 2 9 2
[1, 2, 4, 5, 2, 7, 2, 2] o.k.

Kotlin
1 2 3 4 5 2 6 7 2 9 2 10 20 2 2 2 2 18 2 33 121
[1, 2, 4, 5, 2, 7, 2, 2, 20, 2, 2, 121] difference
C++
1 2 3 4 5 2 6 7 2 9 2 10 20 2 2 2 2 18 2 33 121
[1, 2, 4, 5, 2, 7, 2, 2, 20, 2, 2, 18, 2, 121] difference

Kotlin
1 2 2 2 2 3 4 5 2 6 7 2 9 2 2 2 2 2 2 1 10
[1, 4, 5, 2, 7, 2, 2] difference
C++
1 2 2 2 2 3 4 5 2 6 7 2 9 2 2 2 2 2 2 1 10
[1, 2, 2, 3, 4, 5, 2, 7, 2, 2, 2, 2, 1, 10 ] difference

Kotlin
6 1 6 3 4 5 6 6 7 6 9 6 10 20 6 6 6 33 1
[6, 4, 5, 6, 6, 6, 20, 6, 1] difference
C++
6 1 6 3 4 5 6 6 7 6 9 6 10 20 6 6 6 33 1
[6, 6, 4, 5, 6, 7, 6, 6, 20, 6, 6, 1] difference

Kotlin
1 33 20 1 21 1 1 0
[1, 20, 1, 1] difference
C++
1 33 20 1 21 1 1 0
[1, 20, 1, 1, 0] difference

Nie znam języka "java" ani "kotlin" ale napisałem sobie w C++
i testowałem
dla Kotlin link Online Compilers Kotlin
dla C++ link Online Compilers C++
testy dla Pythona nie przeprowadzałem ponieważ kod z zamieszczonego powyżej listingu zwyczajnie dostaje crash

Chciałbym usunąć numery które występują po duplikatach (w tej liście duplikatem jest liczba 2, ponieważ występuje więcej niż 1 raz)

Moja sugestia
umownie nazwijmy liczbę najczęściej powtarzającą się "wartownikiem"
osobiście bym go nie usuwał
dla testu w programie który napisałem w C++ należy za komentować

Kopiuj

if( (*p == xElement) && (*r != xElement) ) // <--odkomentować
//if( (*p == xElement) ) // <-- zakomentowac

wynik dla przykładowego testu
1 2 2 2 2 3 4 5 2 6 7 2 9 2 2 2 2 2 2 1 10
[1, 2, 2, 2, 2, 4, 5, 2, 7, 2, 2, 2, 2, 2, 2, 2, 10]

Poniżej pełne listingi na jakich testowałem

poniżej algorytm user @watpliwosci

Kopiuj

fun getList(list: MutableList<Int>): MutableList<Int>
 {
    val doubledIndexes = mutableSetOf<Int>()
    val listWithoutDoubled = mutableListOf<Int>()

    list.forEachIndexed { index, item ->
        if (!listWithoutDoubled.contains(item)) {
            listWithoutDoubled.add(item)
        } else {
            doubledIndexes.add(index)
            doubledIndexes.add(list.indexOf(list.find { it == item }))
        }
    }

    val sorted = doubledIndexes.sortedDescending()
    sorted.forEach {
        if (list.getOrNull(it + 1) != null) {
            list.removeAt(it + 1)
        }
    }
    return list
}

fun main(args: Array<String>) {
    
    //val input = mutableListOf(1, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2)
    //val input = mutableListOf(1, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2, 10, 20, 2, 2, 2, 2, 18, 2, 33, 121)
    //val input = mutableListOf(1, 2, 2, 2, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2, 2, 2, 2, 2, 2, 1, 10)
    //val input = mutableListOf(6, 1, 6, 3, 4, 5, 6, 6, 7, 6, 9, 6, 10, 20, 6, 6, 6, 33, 1)
    val input = mutableListOf(1, 33, 20, 1, 21, 1, 1, 0)

    for(el in input)
    {
        print("$el ")
    }
    println()
    print(getList(input))
    
}

poniżej program napisany przeze mnie dla testu

Kopiuj

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <limits>   //std::numeric_limits

using namespace std;

int main()
{
    //vector<int>v = {1, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2}; //output (1, 2, 4, 5, 2, 7, 2, 2)
    //vector<int>v = {1, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2, 10, 20, 2, 2, 2, 2, 18, 2, 33, 121};
    //vector<int>v = {1, 2, 2, 2, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2, 2, 2, 2, 2, 2, 1, 10};
    //vector<int>v = {6, 1, 6, 3, 4, 5, 6, 6, 7, 6, 9, 6, 10, 20, 6, 6, 6, 33, 1};
    vector<int>v = {1, 33, 20, 1, 21, 1, 1, 0};
        
    int nCount = 0, xElement = *(v.begin());
    for(auto & el: v)
    {
        cout << el <<  " ";
        uint16_t c = count(v.begin(), v.end(), el);
        if(c > nCount)
        {   nCount = c;
            xElement = el;
        }
    }
    
    cout << "\n";
    std::vector<int>::iterator p, r;
    p = v.begin(); r = v.begin()+1;

    uint16_t s = v.size();

    for(uint16_t i = 0; i < s-1; ++i)
    {
        //if( (*p == xElement) && (*r != xElement) ) //wartownik to wartownik
        if( (*p == xElement) )
        {
            //cout << "ptr-> " << *r << "\n"; //for test
            p = v.erase(r);
            --s;++r;
        } else {
            ++p;++r;
        }
    }
    
    cout << "[";
    for(auto & el: v)
    {
        cout << el <<  ", ";
    }
    cout << "]\n";

    return 0;
}

Althorion

2022-03-15T09:32:54+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 1620

1

testy dla Pythona nie przeprowadzałem ponieważ kod z zamieszczonego powyżej listingu zwyczajnie dostaje crash

U mnie działa.

[1, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2] → [1, 2, 4, 5, 2, 7, 2, 2] (tak samo jak oba)
[1, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2, 10, 20, 2, 2, 2, 2, 18, 2, 33, 121] → [1, 2, 4, 5, 2, 7, 2, 2, 20, 2, 2, 121] (tak samo jak Kotlin)
[1, 2, 2, 2, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2, 2, 2, 2, 2, 2, 1, 10] → [1, 4, 5, 2, 7, 2, 2] (tak samo jak Kotlin)
[6, 1, 6, 3, 4, 5, 6, 6, 7, 6, 9, 6, 10, 20, 6, 6, 6, 33, 1] → [6, 4, 5, 6, 6, 6, 20, 6, 1] (tak samo jak Kotlin)
[1, 33, 20, 1, 21, 1, 1, 0] → [1, 20, 1, 1] (tak samo jak Kotlin)

Afish

2022-03-15T09:43:43+01:00

Rejestracja: dni
Ostatnio: dni

0

watpliwosci napisał(a):

Czy da się jakos prosciej ?

Jeżeli musisz zmodyfikować wejściową listę, to rób dwoma wskaźnikami, pierwszy wskazuje, gdzie wstawić element, a drugim iterujesz do końca. Potem tylko odcinasz kilka elementów z końca, więc sumarycznie masz złożoność O(N) (o ile usuwanie z końca jest w czasie stałym, ale raczej tak) (i o ile hashset się nie ukwadratowi).

Jeżeli możesz zwrócić nową listę, to robisz to samo, tylko po prostu dorzucasz do nowej listy.

WWA2025

2022-03-15T14:43:43+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 47

0

treść zadania : usunąć numery które występują po duplikatach (w tej liscie duplikatem jest liczba 2, poniewaz wystepuje wiecej niz 1 raz)

input: 1 2 2 2 2 3 4 5 2 6 7 2 9 2 2 2 2 2 2 1 10
output: [1, 4, 5, 2, 7, 2, 2] dla Kotlina & Pythona
output: [1, 2, 2, 3, 4, 5, 2, 7, 2, 2, 2, 2, 1, 10 ] dla C++ (możliwe że błędnie to interpretuje)

Czy może mi ktoś wytłumaczyć co tu się dzieje
dlaczego pomiędzy cyfrą 1 i 4 nie ma żadnej 2 i końcówka też zostaje zjedzona

Althorion

2022-03-15T15:27:21+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 1620

1

Ja to zrozumiałem tak — w tamtej liście są jedynka i dwójka są duplikatami. Zatem pierwsza jedynka zostaje (bo jest pierwsza, więc nie jest po żadnym duplikacie), potem pierwsza dwójka wylatuje, bo jest po duplikacie (jedynce), a kolejne dwójki, bo są po duplikacie (dwójce), i tak aż do czwórki, która wreszcie nie występuje po duplikacie (bo trójka na tej liście jest tylko jedna). A na końcu — jedynka jest usuwana, bo jest po dwójce, a dziesiątka, bo po jedynce. To są nasze znane duplikaty.

Innymi słowy — patrzymy na duplikację globalnie („czy w ogóle występuje druga taka wartość na tej liście?”), nie lokalnie („czy do tej pory wystąpiła już taka wartość?”).

WWA2025

2022-03-15T23:35:20+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 47

0

wstępnie zamieszczam listing ze znalezieniem więcej niż jednego duplikatu,
ale jeszcze nie radzę sobie z usuwanie tych duplikatów tak jak to robi Python czy Kotlin

Kopiuj

//g++ -Wall -fexceptions -g -std=c++17 -c main.cpp -o main.o
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <iomanip>
#include <limits>   //std::numeric_limits

using namespace std;

int main()
{
    //vector<int>v = {1, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2};
    vector<int>v = {1, 2, 2, 2, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2, 2, 2, 2, 2, 2, 1, 10};
    //vector<int>v = {1, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2, 10, 20, 2, 2, 2, 2, 18, 2, 33, 121})
    //vector<int>v = {1, 33, 20, 1, 21, 1, 1, 0};

    std::map<int, int> maska;

    for(auto & el: v)
    {
        cout << el << " ";
        uint16_t w = count(v.begin(), v.end(), el);
        if(w > 1) maska[el] = w;
    }

    cout << "\n\n";
    for(const auto& el: maska)
        cout << "num " << setw(3) << right << el.first << " count " << setw(3) << right  << el.second << "x\n";
    //for(auto const& [key, val] : maska) //only -std=c++17
        //cout << key << " " << val << "\n";

    cout << "\n-----------------------\n";
    std::vector<int>::iterator p, r;
    std::map<int, int>::iterator it;
    p = v.begin(); r = v.begin()+1;
    it = maska.begin();

    uint16_t s = v.size();
    uint16_t m = maska.size();

    for(uint16_t i = 0; i < m; ++i)
    {
        for(uint16_t j = 0; j < s-1; ++j)
        {
            //cout << "p " << *p << " r " << *r << " it->first " << it->first << "\n";
            //if( (*p == it->first) && (*r != it->first) )
            if( *p == it->first )
            {
                p = v.erase(r);
                --s;++r;--it;
            } else {
                ++p;++r;++it;
            }
            if( *p != it->first ){++it;}
            else{--it;}
        }

    }

    uint8_t k = 0;
    cout<<"[";
    for(const auto & el: v)
    {
        if(k<v.size()-1)cout<<el<<", ";
        else cout<<el;
        ++k;
    }
    cout << "]\n";

    return 0;
}

MarekR22

2022-03-16T17:49:07+01:00

Rejestracja: dni
Ostatnio: dni

2

https://godbolt.org/z/6Y46fTqWc

WWA2025

2022-03-17T00:00:54+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 47

0

histogram_from w funkcji tej zliczasz duplikaty i umieszczasz w mapie i zwracasz mape to rozumiem
copy_drop_after_duplicates w tej funkcji nie za bardzo rozumiem tej lambdy
funkcja przyjmuje 3 argumenty początek tablicy arr, koniec tablicy arr, i vector result
const auto hist przyjmuje argument zwrócony z histogram_from, czyli kontener std::unordered_map
a dokładnie nie rozumiem tego zapisu

Kopiuj

[&copyNext, &hist](const auto& x) {
return std::exchange(copyNext, hist.at(x) <= 1)

uczę się przerabiając Twój kod

Kopiuj

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iterator>         // std::back_inserter
#include <iomanip>

using namespace std;


std::unordered_map<int, int> histogram_from(vector<int> arr)
{
    std::unordered_map<int, int> hist;
    for(const auto & el: arr)
    {
        uint16_t w = count(arr.begin(), arr.end(), el);
        if(w > 1) hist[el] = w;
    }
    return hist;
}

std::vector<int> copy_drop_after_duplicates(vector<int> arr, vector<int> &out)
{
    std::unordered_map<int, int> hist = histogram_from(arr);
    bool copyNext = true;

    std::vector<int>::iterator b, e;
    b = arr.begin(); e = arr.end();
    
    for(const auto el: arr)
    {
        //cout << el << " ";    
        out.push_back(el);
    }   
    return out;
    /*return std::copy_if(b, e, out, [&copyNext, &hist](const auto& x) {
    return std::exchange(copyNext, hist.at(x) <= 1);
});
  */
}

int main()
{

    vector<int> arr = {1, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2};
    //vector<int> arr = {1, 2, 2, 2, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2, 2, 2, 2, 2, 2, 1, 10};
    //vector<int> arr = {1, 2, 3, 4, 5, 2, 6, 7, 2, 9, 2, 10, 20, 2, 2, 2, 2, 18, 2, 33, 121};
    //vector<int> arr = {1, 33, 20, 1, 21, 1, 1, 0};

    std::vector<int> result;
    result.reserve(arr.size());

    for(auto &a : arr)
        cout << a << " ";
    cout << "\n";

    //jeszcze nie funkcjonuje
    copy_drop_after_duplicates(arr, result);

    cout << "\n";
    std::unordered_map<int, int> hist = histogram_from(arr);

    for(const auto& el: hist)
        cout << "num " << setw(3) << right << el.first << " count " << setw(3) << right  << el.second << "x\n";
    
    cout << "\nresult\n";
    for(const auto &s : result)
        cout << s << " ";

    return 0;
}

MarekR22

2022-03-17T00:06:57+01:00

Rejestracja: dni
Ostatnio: dni

1

WWA2025 napisał(a):

a dokładnie nie rozumiem tego zapisu
Kopiuj
[&copyNext, &hist](const auto& x) {
return std::exchange(copyNext, hist.at(x) <= 1);

std::exchange zwraca starą wartość copyNext, które równocześnie nadpisuje wartością hist.at(x) <= 1 (jest to zgrabniejsze rowiązanie, niż użycie zmiennej tymczasowej),
bo w końcu poprzednia wartość wejścia ma wpływ na to, że obecna ma być skopiowana lub nie.

WWA2025

2022-03-20T09:25:12+01:00

Rejestracja: dni
Ostatnio: dni
Postów: 47

1

@watpliwosci przepraszam, że zrobiłem off-topic

Dziękuję @Althorion za wyrozumiałość i zwrócenie uwagi
Dziękuję @MarekR22 za udostępnienie swojego rozwiązania, dzięki temu mogłem zrozumieć i napisać swoje