Losowa lista z innej listy. Najszybszy algorytm.

Odpowiedz Nowy wątek
2020-02-13 00:09

Rejestracja: 4 lata temu

Ostatnio: 1 tydzień temu

0

Witam. Mam listę
a = [1,2,3,4,5]
Jak można szybko utworzyć listę B z losowymi elementami listy a. Elementy nie mogą się powtarzać. Czyli jak pomieszać losowo listę a? Mam np. 16 milionów elementów. Trwa to bardzo długo. Czy istnieje szybki sposób?

Czy liczby w liście a to ciąg liczb rosnących? Ile będziesz miał list takich jak B? Jakiej wielkości będą listy B? - devpython 2020-02-13 10:50

Pozostało 580 znaków

2020-02-13 00:23

Rejestracja: 5 lat temu

Ostatnio: 1 godzina temu

Lokalizacja: Chorzów

1

Na wejściu i wyjściu musi być lista czy może być tablica ?
Z zapisu wynika, że masz tablicę.

Tak ogólnie to musisz poszukać algorytmów tasowania.
Pracując na tablicy losuje się 2 indeksy i zamienia wartości miejscami.
W sumie na liście też można użyć 2 wskaźniki i zamieniać wartości.


Projektowanie i programowanie. Hobbystycznie elektronika i audio oszołom.
edytowany 3x, ostatnio: katakrowa, 2020-02-13 00:31
Z zapisu wynika, że masz tablicę. Ten zapis oznacza listę w pythonie. https://docs.python.org/3.5/t[...]structures.html#more-on-lists Pod spodem to wskaźnik na wskaźniki, ale Jak przechodzi się z innych języków to nazewnictwo faktycznie może się mylić ;-) - devpython 2020-02-13 10:57
W Pythonie mówi się "lista", ale jest to tak naprawdę dynamiczna tablica, a nie lista z dowiązaniami. - enedil 2020-02-13 14:45
@endil: tak mi się wydawało ale się nie odzywałem bo w Pythonie nie piszę wcale. Implementowałem jedynie quickSort'a i kilka prostych algorytmów żeby zmierzyć wydajność interpretera na elementarnych operacjach i wówczas używałem takiej struktury jako tablicy... ale kto tam wie co rzeczywiście dzieje cię w interpreterach :-) - katakrowa 2020-02-13 14:50

Pozostało 580 znaków

2020-02-13 00:40

Rejestracja: 4 lata temu

Ostatnio: 1 tydzień temu

0

O tym nie pomyślałem. Dzięki.
Z zapisu wynika, że masz tablicę. A jaka róznica między listą, a tablicą? Są tablice w pythonie? Sorki, ale nie wiem.

edytowany 3x, ostatnio: xenix33, 2020-02-13 00:47

Pozostało 580 znaków

2020-02-13 01:05

Rejestracja: 8 miesięcy temu

Ostatnio: 4 dni temu

1

A nie wystarczy Ci najprostsze rozwiązanie ?

a = [1,2,3,4,5]
b = a[:]
random.shuffle(b)

Pozostało 580 znaków

2020-02-13 01:14

Rejestracja: 4 lata temu

Ostatnio: 1 tydzień temu

0

W pythonie pisze 2 lata, ale wciąż mnie zaskakuję. Dzięki.

edytowany 2x, ostatnio: xenix33, 2020-02-13 01:17

Pozostało 580 znaków

2020-02-13 10:30

Rejestracja: 3 lata temu

Ostatnio: 1 godzina temu

0

Czas algorytmu shuffle jest liniowy, dla dużych tablic będzie to zawsze trochę trwało.


A da się szybciej ? Zresztą - w "wymaganiach" miał, że w wyniku ma powstać nowa lista więc co byś nie robił to i tak to będzie co najmniej O(n)... - Bartłomiej Golenko 2020-02-13 14:47
lion A jak szybciej chcesz zrobić losową permutacje N-elementowej list? o_O - Shalom 2020-02-15 14:45
Nie chcę szybciej, tyły to zajmuje po prostu - lion137 2020-02-15 17:54

Pozostało 580 znaków

Odpowiedz

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