Michał M. konsultant IT
Piotr G.:
Jeśli ID byłyby posortowane, to się da - średnio o połowę krócej.
Oczywiście przy założeniu, że koszt operacji arytmetycznych jest pomijalny w porównaniu z kosztem operacji bazodanowych (co jest zwykle prawdą).
Ale dla nieposortowanych danych? Hmmm...
Piotr
Głudkowski
Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...
Przemysław R.:
Błażej O.:Ten piwocik był po to aby można było problem rozwiązać metodą ekspercką ;-)))
w pewnych kręgach poczucie bycia niezastąpionym jest bezcenne ;)
Piotr
Głudkowski
Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...
Michał Matląg:
Piotr G.:
Jeśli ID byłyby posortowane, to się da - średnio o połowę krócej.
Oczywiście przy założeniu, że koszt operacji arytmetycznych jest pomijalny w porównaniu z kosztem operacji bazodanowych (co jest zwykle prawdą).
Ale dla nieposortowanych danych? Hmmm...
Zakładałem, że dane są posortowane.
Piotr
Głudkowski
Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...
Błażej
O.
Badania i rozwój
zaawansowanych
systemów
analitycznych
Piotr G.:
Błażej O.:
Michał Matląg:
Właśnie sobie przeczytałem kilka postów dotyczących zagadki i wydaje mi się, że można to zrobić bez użycia funkcji SUM, czy innych funkcji agregujących co najmniej na 2 inne sposoby, ale jeszcze jutro sprawdzę to w praktyce żeby potwierdzić ;-))
No właśnie czy ten algorytm opisany przez kolegę Piotra jest najszybszy - czy też może istnieje coś lepszego?
A to ci dopiero zagadka??? -> mamy jeszcze 50 minut ...
Podpuszczasz czy wiesz, że jest?
Bez indeksów i żadnych pomocniczych struktur?
Lepszy niż O(n)????? Hmmm...
Błażej
O.
Badania i rozwój
zaawansowanych
systemów
analitycznych
Piotr G.:
Michał Matląg:
Piotr G.:
Jeśli ID byłyby posortowane, to się da - średnio o połowę krócej.
Oczywiście przy założeniu, że koszt operacji arytmetycznych jest pomijalny w porównaniu z kosztem operacji bazodanowych (co jest zwykle prawdą).
Ale dla nieposortowanych danych? Hmmm...
Zakładałem, że dane są posortowane.
W początkowych założeniach nie było o tym mowy. A więc należało założyć, że nie są :)
Generalnie założenie było, że nie korzystamy z indeksów. A w takim przypadku w SQL nie można zakładać jakiegokolwiek porządku danych, bo nawiet, jeśli były zapisywane kolejno, nie ma żadnej gwarancji, że tak będą czytane.Piotr G. edytował(a) ten post dnia 17.03.10 o godzinie 23:40
Piotr
Głudkowski
Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...
Błażej
O.
Badania i rozwój
zaawansowanych
systemów
analitycznych
Piotr G.:
Dla danych posortowanych da się osiągnąć złożoność O(log2(n)) - pod warunkiem, że pominiemy koszt WHERE.
Ale WHERE bez indeksu przecież będzie miał złożoność rzędu średnio O(n/2).
Chyba, że jest jakiś sposób na wyciąganie rekordu o określonym numerze bez konieczności jego wyszukiwania WHERE-m.
Piotr
Głudkowski
Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...
Piotr Wolański Programista
Piotr
Głudkowski
Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...
konto usunięte
Piotr G.:
Krzysztof Drelczuk:
Ja tam nie widzę żadnych znaków mnożenia. Tak więc pytanie ma taki sam sens jak: jaki jest wynik a:b ;p
Z definicji, która była jeszcze w podstawówce:
2x = 2 * x
Czyli są znaki mnożenia, choć ich nie widać.
Piotr Wolański Programista
Piotr G.:
Marcin N.:
SELECT ID
FROM Tabela
GROUP BY ID
HAVING COUNT(*) > 1
...i w ten sposób mamy zdublowane ID
Super. A jaki będzie koszt (a przede wszystkim rząd kosztu) takiego zapytania dla tego miliona jeden rekordów??? Mówiąc krótko, po jakim czasie dostaniesz wynik, jeśli baza stoi na niezbyt wypasionej maszynie?
Piotr
Głudkowski
Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...
Krzysztof Drelczuk:
Piotr G.:
Krzysztof Drelczuk:
Ja tam nie widzę żadnych znaków mnożenia. Tak więc pytanie ma taki sam sens jak: jaki jest wynik a:b ;p
Z definicji, która była jeszcze w podstawówce:
2x = 2 * x
Czyli są znaki mnożenia, choć ich nie widać.
Ja tam takiej definicji nie pamiętam, ale może. To dawno temu było. Ale czy to oznacza, że tgx = t*g*x ? ;)
Piotr
Głudkowski
Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...
Piotr Wolański:
No dobra sprawdziłem to w praktyce.
Tabela 45.000.000 rekordów (ok. 3 GB)
count(*) - 30 s.
sum(ID) - 30 s.
wersja z HAVING - ok 210 s.
co ciekawe takie coś jak ponizej też działa ok 140 s.:
SELECT ID, rn FROM
( SELECT ID, rownum rn FROM ...
ORDER BY ID )
WHERE ID != rn
I najciekawsza wersja ale trochę wolniejsza ok. 330 s.:
SELECT ID FROM (
SELECT ID, ID-LAG(ID,1) OVER (ORDER BY ID) diff FROM ...
) WHERE diff = 0
a wersja jest "najciekawsza" bo jak zmienimy warunek na diff>1
to mamy listę "dziur" w numeracji
Łukasz Schabek Architekt Rozwiązań
Piotr
Głudkowski
Rzucam się na
wszystko to, co jest
ciekawe i wymaga
rusze...
Łukasz Schabek:
Piotr Wolański Programista
Piotr G.:
Piotr Wolański:
No dobra sprawdziłem to w praktyce.
Tabela 45.000.000 rekordów (ok. 3 GB)
count(*) - 30 s.
sum(ID) - 30 s.
wersja z HAVING - ok 210 s.
co ciekawe takie coś jak ponizej też działa ok 140 s.:
SELECT ID, rn FROM
( SELECT ID, rownum rn FROM ...
ORDER BY ID )
WHERE ID != rn
Piotr, a osiągniesz takie wyniki na mocno obciążonej maszynie (chodzi mi oczywiście o buforowanie)?
konto usunięte
Piotr Wolański:
Piotr G.:
Piotr Wolański:
No dobra sprawdziłem to w praktyce.
Tabela 45.000.000 rekordów (ok. 3 GB)
count(*) - 30 s.
sum(ID) - 30 s.
wersja z HAVING - ok 210 s.
co ciekawe takie coś jak ponizej też działa ok 140 s.:
SELECT ID, rn FROM
( SELECT ID, rownum rn FROM ...
ORDER BY ID )
WHERE ID != rn
Piotr, a osiągniesz takie wyniki na mocno obciążonej maszynie (chodzi mi oczywiście o buforowanie)?
Jeżeli obciążenie nie będzie sięgac do dysku...
W tym konkretnym przypadku takie wyniki to kwestia wydajności dysków (w pomiarach tylko 20 MB/s :( przy kopiowaniu dużych plików)
3GB/20 MB/s = 150 sek.
Przy count(*) i sum(ID) - ORACLE sięga tylko po danych indeksu a tych jest 10 razy mniej
Piotr Wolański Programista
Kruczki i sztuczki.
Sposób na wyciągnięcie duplikatów z kolumny dowolnego typu:
select *
from nazwatabeli a, nazwatabeli b
where a.kolumna=b.kolumna;
I tyle, i to wystarczy, jak powiedziano w pewnej reklamie.
Następna dyskusja:
пропозиції роботи
