Pchełki SQL, odcinek 7: 1000

Pisałem niedawno o zagadnieniu wyszukiwania trójek liczb trzycyfrowych sumujących się dokładnie do 1000, z dziewięciu różnych cyfr.

Butter zapodał w komentarzach przykładowe rozwiązanie w SQL-u, a także zasugerował, że można by je zoptymalizować pod kątem wydajności. Kod, który podał, wykonywał się u mnie około czterech i pół minuty.

Siadłem więc do tematu i oto urodziła się kolejna pchełka SQL. Mój kod pokrywa się w większości z pomysłem Buttera, podrasowałem go tylko tu i ówdzie.

Po pierwsze, pozbyłem się kosztownych operacji na stringach.

Po drugie, dodałem warunek odrzucający liczby, w których na pozycji setek znajdują się cyfry nie sumujące się dokładnie do dziesięciu (włączając w to ewentualne przeniesienie z pozycji dziesiątek).

Po trzecie wreszcie, pozbyłem się duplikatów (korzystając z naprzemienności dodawania, zredukowałem ilość trójek na wyjściu z 1080 do 180)

W ten oto sposób powstał kod, który wykonuje się w niecałe pół sekundy. Oto on:

with licz as
( select 0 x
  union all select x + 1
  from licz
  where x < 9
)
, jed as
( select
	l1.x x1,
	l2.x x2,
	l3.x x3,
	(l1.x + l2.x + l3.x) / 10 as jed10 
  from licz l1, licz l2, licz l3
  where
	l1.x <> l2.x and
	l1.x <> l3.x and
	l2.x <> l3.x
	and
	(l1.x + l2.x + l3.x) % 10 = 0
	and
	(l1.x < l2.x and l2.x < l3.x)
) 
, dzie as
( select
	jed.x1 jx1,
	jed.x2 jx2,
	jed.x3 jx3,
	l1.x dx1,
	l2.x dx2,
	l3.x dx3,
	(jed10 + l1.x + l2.x + l3.x) / 10 as dzie10 
  from licz l1, licz l2, licz l3, jed
  where
	l1.x <> l2.x and
	l1.x <> l3.x and
	l2.x <> l3.x
	and
	l1.x not in (jed.x1, jed.x2, jed.x3) and
	l2.x not in (jed.x1, jed.x2, jed.x3) and
	l3.x not in (jed.x1, jed.x2, jed.x3)
    and 
	10 - ((l1.x + l2.x + l3.x) % 10) = jed10
  )
 , setki as (
  select
	l1.x sx1,
	l2.x sx2,
	l3.x sx3,
	dzie.dx1,
	dzie.dx2,
	dzie.dx3,
	dzie.jx1,
	dzie.jx2,
	dzie.jx3
  from licz l1, licz l2, licz l3, dzie
  where
	l1.x <> l2.x and
	l1.x <> l3.x and
	l2.x <> l3.x
	and
	0 not in (l1.x, l2.x, l3.x)
	and
	l1.x not in (dzie.dx1, dzie.dx2, dzie.dx3, dzie.jx1, dzie.jx2, dzie.jx3) and
	l2.x not in (dzie.dx1, dzie.dx2, dzie.dx3, dzie.jx1, dzie.jx2, dzie.jx3) and
	l3.x not in (dzie.dx1, dzie.dx2, dzie.dx3, dzie.jx1, dzie.jx2, dzie.jx3)
	and
	10-((l1.x+l2.x+l3.x) % 10) = dzie10
)
select
	sx1 * 100 + dx1 * 10 + jx1 l1,
	sx2 * 100 + dx2 * 10 + jx2 l2,
	sx3 * 100 + dx3 * 10 + jx3 l3
from setki
where sx1 * 100 + dx1 * 10 + jx1 + sx2 * 100 + dx2 * 10 + jx2 + sx3 * 100 + dx3 * 10 + jx3 = 1000;

Odrobina wyjaśnień:

Pierwsze CTE (licz), generuje jednokolumnową listę liczb od zera do dziewięciu.

Drugie CTE (jed) generuje wszystkie trójki ostatnich cyfr (czyli cyfr na pozycji jednostek) takie, że:
- ich suma dzieli się przez 10
- są posortowane rosnąco (właśnie tutaj usuwamy duplikaty!)
- są różne
Oprócz tego w tym CTE wyliczamy również cyfrę przeniesienia do kolumny dziesiątek (jed10), która wynosi zawsze 1 lub 2.

Trzecie CTE (dzie) zwraca siedem kolumn: trzy kolumny z poprzedniego CTE (a więc kolumna jedności), trzy kolumny z cyframi dziesiątek, oraz wartość przeniesienia do kolumny setek. Uwzględniamy tutaj wartość przeniesienia z kolumny jedności, zapewniamy, że wszystkie cyfry mają być różne (a także różne od tych użytych w kolumnie jedności), oraz że ich suma, wraz z nadmiarem przeniesionym z kolumny jedności, ma być podzielna przez 10.

Czwarte CTE (setki) robi dokładnie to samo co poprzednie, z tą tylko różnicą, że wykluczamy zero (liczba trzycyfrowa nie może zaczynać się od zera).

Wreszcie końcowe zapytanie zwraca te z liczb, których suma wynosi tysiąc.

Ciekawostką jest, że faktycznie - jak poprawnie odgadł B - jedyną cyfrą, którą można wyeliminować z zakresu 0-9 jest ósemka; w tym przypadku suma pozostałych cyfr wynosi 37 a więc - zgodnie z rozważaniami pokazanymi przez B - da się takie trójki zbudować.

15 komentarzy

  1. przyznaje się bez bicia – robiłem to tylko dla [poprawnego?] wyniku. Wydajność faktycznie mogła by być lepsza. Btw:

    0 not in (l1.x, l2.x, l3.x) można zastąpić l1.x * l2.x * l3.x !=0 [ale czy jest szybsze – nie wiem ;)]

    Butter

  2. Skoro Ty taki mistrz zagwozdek jesteś, to może pomożesz mi z moim problemem parainformatycznym. Akcja dzieje się w Excelu. Mamy tabelę, powiedzmy 20×10, choć to akurat jest nieistotne i podaje tylko dla pełnej plastyki opisu. W tabelę wpisujemy liczby od 1 do 99 (w kolejności losowej). Jeśli zadanie wykona się poprawnie, żadna liczba się nie powtarza. Niestety wielokrotnie się mylę i tu pytanie. Jaka formuła znajdzie mi w tabeli liczbę lub liczby, które się powtarzają? Ewentualnie liczby z zakresu 1 do 99, których brakuje?

    1. jak masz tabele 10×20 to nie ma bata, żeby liczby 1-99 się nie powtarzały ;).

      W nowym excelu [>=2007] masz: formatowanie warunkowe / reguły wyróżniania komórek / duplikujące się wartości.

      jeśli chcesz sprawdzić unikalność wartości, to użyj: =LICZ.JEŻELI(obszar_przeszukiwania;wartość)

    2. Jak już Butter nadmienił, nie ma bata, jak masz 200 komórek i tylko 99 liczb, nie da się bez dubli. Wyjaśnij zatem dokładniej o co chodzi z tym unikaniem powtórzeń.

      Pachnie mi to jakąś pchełką VBA, ale bez szczegółów dalej nie pójdę.

  3. Tabela zawiera puste komórki panowie 🙂

    Formuła LICZ.JEŻELI ciut na piechotę, ale załatwi sprawę. Dzięki serdeczne.

    Spróbowałbym jeszcze tego formatowania warunkowego, ale … nie wiem gdzie tą opcje znaleźć. No co? Nie każdy jest informatykiem 😉

    1. OK czyli chcesz w 200 pustych komórek wstawić 99 liczb całkowitych od 1 do 99 tak, żeby się nie powtarzały? Czyli, innymi słowy, niektóre komórki pozostaną puste?

        1. <pre>Public Sub FillRandom(ByRef r As Excel.Range, ByVal n As Integer)

          If r.Count < n Then

          MsgBox "Nidyrydy, za mało komórków!", vbOKOnly + vbCritical

          Exit Sub

          End If

          Dim x As Integer, y As Integer, counter As Integer

          Randomize

          counter = 1

          Do While counter <= n

          x = 1 + Round(Rnd * (r.Columns.Count – 1))

          y = 1 + Round(Rnd * (r.Rows.Count – 1))

          If r.Cells(y, x) = "" Then

          r.Cells(y, x).Value = counter

          counter = counter + 1

          End If

          Loop

          End Sub

          </pre>

          Przykład użycia:

          <pre>fillrandom range("A1:J20"), 100</pre>

          Smacznego!

        2. A tu masz alternatywne rozwiązanie:

          <pre>

          Option Explicit

          Option Base 0

          Public Sub FillRandom2(ByVal r As Excel.Range, n As Integer)

          If n > r.Count Then

          MsgBox "Za dużo liczb, za mało komórek", vbOKOnly + vbCritical

          Exit Sub

          End If

          Dim a() As String

          ReDim a(r.Count – 1)

          Dim i As Integer

          Dim c As Excel.Range

          Dim tmp_addr As String

          i = 0

          For Each c In r.Cells

          a(i) = c.Address

          i = i + 1

          Next c

          Dim x As Integer, y As Integer

          Randomize

          For i = 1 To n * 5

          x = Rnd * (r.Count – 1)

          y = Rnd * (r.Count – 1)

          tmp_addr = a(x)

          a(x) = a(y)

          a(y) = tmp_addr

          Next i

          For i = 0 To n – 1

          Range(a(i)).Value = i + 1

          Next i

          End Sub

          </pre>

          Sposób użycia analogiczny jak poprzednio.

          Smacznego 😉

          1. Kurcze Xpil, Twój kolega Butter bardzo mnie pomógł, ale Ty to mnie chyba najzwyczajniej obrażasz ;). Z tym 'nidyrydy…' bardzo zabawne , przyznaję. Ale ja jestem zwykłym śmiertelnikiem, z tymi wszystkimi integerami i x-ami, to ja nawet nie wiedziałbym co zrobić, choć nie ma to znaczenia, bo chyba źle mnie zrozumiałeś.

            To jest jeden z moich obowiązków służbowych. Tabelę wypełniam sam. Według określonego porządku (nie ma co wdawać się w rozwiązłe szczegóły), tylko często popełnię błąd i jedna liczba wpisana jest dwukrotnie, podczas gdy innej brakuje.

            Wtedy kopiuje wszystkie liczby do jednej kolumny, ustawiam w kolejności numerycznej i ręcznie znajduje winnego. Myślałem, że jest prostsza metoda i nie myliłem się, bowiem przy użyciu formuły licz.jeżeli, utworzę sobie taką kolumnę na boczku, która mi automatycznie powie, gdzie jest błąd.

            To co Ty mi podałeś na tacy – o ile rozumiem, a rozumieć nie mam prawa – w losowy sposób wypełnia tabelę liczbami całkowitymi od 1 do 99.

            Niemniej serdeczne dzięki za czas i zaangażowanie :). Pzdr

          2. MisZa, pozwól, że Cię zacytuję:

            "W tabelę wpisujemy liczby od 1 do 99 (w kolejności losowej). Jeśli zadanie wykona się poprawnie, żadna liczba się nie powtarza."

            Potem jeszcze się upewniłem: "chcesz w 200 pustych komórek wstawić 99 liczb całkowitych od 1 do 99 tak, żeby się nie powtarzały?" – "Exactly!"

            Tak więc wyspecyfikowałeś zagadnienie (dwukrotnie!) w taki sposób, że trzeba wypełnić dwieście komórek losowymi, unikalnymi wartościami, a teraz się wykręcasz.

            Ale, jak by to powiedzieć, przywykłem. I tak jest dobrze, że jest ciebie tylko jedna sztuka. Przy większych projektach sam etap specyfikowania wymagań potrafi zająć parę miesięcy, a i tak potem są pretensje, że dostarczono kwadraty, a przecież wyraźnie było mówione, że mają być kółka 😉

            Co zaś do problemu, który faktycznie potrzebujesz rozwiązać, to alternatywą dla formuły, którą podał Butter, może być opcja podświetlania duplikatów (na pewno jest w wersji Office 2007 i późniejszych, nie wiem jak przedtem).

            Zaznaczasz zakres do szukania duplikatów, a następnie: Home => Conditional Formatting => Highlight Cell Rules => Duplicate Values.

  4. No nie przyjacielu, manipulujesz moją wypowiedzią. Druga cytowana wypowiedź faktycznie nie jest najszczęśliwiej sformułowana, choć jak najbardziej prawdziwa. Niemniej potrafię zrozumieć skąd nieporozumienie. Natomiast pierwszą zakończyłem pytaniem:

    "Jaka formuła znajdzie mi w tabeli liczbę lub liczby, które się powtarzają? Ewentualnie liczby z zakresu 1 do 99, których brakuje?"

    I to było szukanym w zadaniu. Butte, załapał 😉

    Ale. Żeby nie było, że do rabego po pomoc poszedł i jeszcze psioczy. Dzięki śliczne za pomoc. W pracy excela mam archaicznego na formatowanie warunkowe szans nie ma. Z licz.jeżeli też nie jest łatwo, bo office angielski i nie mogę odnaleźć odpowiadającej formuły. Najbliżej byłem z dcount, ale ta robi robotę tylko dla wskazanej kolumny w tabeli.

    MiSzA jest smutny

  5. jedn[..] where

    l1.x l2.x and l1.x l3.x and l2.x l3.x

    [..]

    and (l1.x < l2.x and l2.x < l3.x)

    imho te 2 warunki są redundantne – wystarczy 2gi

  6. Zgadza się. Ponadto końcowy warunek (=1000) można zapisać za pomocą dwóch mnożeń.

    Jak się do tego zastąpi rekurencję w pierwszym CTE zwykłym UNION SELECT… i wyeliminuje ósemkę, czas wykonania spada do 40 milisekund (pi x oko)

Leave a Comment

Twój adres e-mail nie zostanie opublikowany.