Witaj Gościu! ( Zaloguj | Rejestruj )

Forum PHP.pl


Anagramacja (permutacja), scrabble i zapytanie MySQL
Aztech
Napisane: 11.02.2010, 10:39:56





Grupa: Zarejestrowani
Postów: 276
Dołączył: 22.10.2003
Skąd: Wrocław

Ostrzeżenie: (0%)
-----
Proponuję zapoznanie się z pracą Daniela Janusa na temat systemu Pliquarp, który służy do wyszukiwania słów w Korpusie języka Polskiego (używanego w PWN), no i przede wszystkim polecam przeczytanie książki Knutha o generowaniu wszystkich krotek i permutacji.
Po tej lekturze na pewno przyjdzie Ci jakieś rozwiązanie do głowy biggrin.gif.
Co możesz zrobić (ja tak zrobiłem w swoim programie działającym a'la OSPS/Anagramator to:
I1) stworzyć dodatkową indeksowaną kolumnę zawierającą informację o długości słowa
I2) stworzyć dodatkową indeksowaną kolumnę zawierająca pierwszą literę wyrazu
I3) stworzyć dodatkową kolumnę zawierającą wszystkie litery z wyrazu posortowane od A do Z
Zadawanie zapytania do bazy wyglądałoby następująco:
Z1) Bierzesz wszystkie litery (bez blanków) i tworzysz z nich wszystkie permutacje
Z2) Bierzesz blanki podstawiasz po kolei literki A-Z, tworząc permutacje
Z3) Robisz permutacje obu tych zbiorów, a następnie usuwasz duplikaty, sortujesz litery od A-Z
Z4) Przesyłasz zapytanie do bazy, korzystając z indeksów: I1 oraz I3

Mój programik, napisany w podobny, do powyższego algorytmu, sposób generuje losowo 100 słów 7 literowych a następnie przeszukuje całą bazę, czy nie ma w nim przypadkiem innych słów z tych samych liter. Cały proces, PHP + baza MySQL (MyISAM) + framework PRADO wykonują to zadanie (bez żadnych cache'ów i akceleratorów) w ok 1,5 minuty (1 słowo wraz z permutacjami ok 0,5 sek).

P.S. Proponuję również zapoznać się z tym wątkiem
P.S.2. Aby zoptymalizować twoje zapytanie, dodaj indeks do kolumn z ilością wystąpień danej litery
P.S.3 Aha, jest jeszcze algorytm Knutja-Morrisa-Pratta
  Forum: Bazy danych · Podgląd postu: #712114 · Odpowiedzi: 5 · Wyświetleń: 1 847

[MYSQL] Wyszukiwanie w bazie strasznie wolne.
Aztech
Napisane: 18.01.2008, 08:19:34





Grupa: Zarejestrowani
Postów: 276
Dołączył: 22.10.2003
Skąd: Wrocław

Ostrzeżenie: (0%)
-----
Polecam Ci przeczytanie artykułu Jak działa MySQL na EIOBA. Polcam Ci też ostatnie wydanie phpSolutions, znajdziesz tam artykuł MySQL - Techniki przyśpieszania zapytań. Gazetka kosztuje 30zł, ale to wydanie wyjątkowo jest warte swojej ceny.
Z ciekawych artykułów poczytaj sobie tu i tu i na koniec artykulik w wiki
  Forum: Przedszkole · Podgląd postu: #431705 · Odpowiedzi: 10 · Wyświetleń: 1 880

[MYSQL] Wyszukiwanie w bazie strasznie wolne.
Aztech
Napisane: 16.01.2008, 15:28:43





Grupa: Zarejestrowani
Postów: 276
Dołączył: 22.10.2003
Skąd: Wrocław

Ostrzeżenie: (0%)
-----
Strasznie masz zrobioną tą bazę:
- po pierwsze jeśli masz tabelę dane, to trzymaj w niej id modelu a nie referencję do modelu, dlatego że jeśli trzymasz tam tekst to podczas JOINa masz robione porównywanie tekstów, które jest strasznie wolne
- w tabelkach osobowe_* używasz do id typów INT, po co Ci takie duże? Jeśli nie masz tam dużo danych skorzystaj z dobordziejstwa typów TINYINT, SMALLINT, MEDIUMINT
- w tabelce dane masz np marka, która jest typu smallint(11), natomiast w tabeli osobowe_marka masz id jako int(11) => niekonsekwencja
- poznaznaczaj sobie w polach UNSIGNED (id raczej ujemne nie będzie biggrin.gif)
- poprawiłem trochę twoją bazę danych (poniżej kod) pozakładałem klucze obce, potworzyłem indeksy oraz zmieniłem typ na InnoDB
- proponowałbym Ci buforowanie odczytów, czyli wybierasz tak narapwdę tylko z bazy danych dane a następnie tylko i wyłącznie dla wyświetlanych aktualnie wierszy odczytujesz odpowiednie informacje z tabelek sobowe_*
- całej tabelki dane nie chciało mi się modyfikować

Rada:
ściągnij sobie ze strony MySQL (Administrator, Query Browser) i korzystaj z nich

Kod
SET SQL_MODE="NO_AUTO_VALUE_ON_ZERO";
--
-- Struktura tabeli dla  `dane`
--

CREATE TABLE `dane` (
  `id_dane` int(11) NOT NULL auto_increment,
  `id_uzytkownika` int(11) NOT NULL,
  `firma_prywatnie` char(1) default NULL,
  `data_dodania` datetime default NULL,
  `data_aktywacji` datetime default NULL,
  `status` char(1) default NULL,
  `wyroznione` year(4) default NULL,
  `fotografie` char(1) default NULL,
  `kategoria` int(11) default NULL,
  `typ_oferty` char(1) default NULL,
  `id_marka` int(10) unsigned NOT NULL,
  `id_model` int(10) unsigned NOT NULL,
  `id_typ` int(10) unsigned NOT NULL,
  `rocznik` smallint(11) default NULL,
  `miesiac` varchar(3) default NULL,
  `przebieg` int(11) default NULL,
  `cena` int(11) default NULL,
  `region` char(2) default NULL,
  `typ_silnika` char(10) default NULL,
  `silnik` varchar(2) default NULL,
  `pojemnosc` char(5) default NULL,
  `moc` char(5) default NULL,
  `typ_nadwozia` char(2) default NULL,
  `drzwi` char(2) default NULL,
  `kolor` varchar(20) default NULL,
  `o_1` char(1) default NULL,
  `o_2` char(1) default NULL,
  `o_3` char(1) default NULL,
  `o_4` char(1) default NULL,
  `o_5` char(1) default NULL,
  `o_6` char(1) default NULL,
  `o_7` char(1) default NULL,
  `o_8` char(1) default NULL,
  `o_9` char(1) default NULL,
  `o_10` char(1) default NULL,
  `o_11` char(1) default NULL,
  `o_12` char(1) default NULL,
  `o_13` char(1) default NULL,
  `o_14` char(1) default NULL,
  `o_15` char(1) default NULL,
  `w_1` char(1) default NULL,
  `w_2` char(1) default NULL,
  `w_3` char(1) default NULL,
  `w_4` char(1) default NULL,
  `w_5` char(1) default NULL,
  `w_6` char(1) default NULL,
  `w_7` char(1) default NULL,
  `w_8` char(1) default NULL,
  `w_9` char(1) default NULL,
  `w_10` char(1) default NULL,
  `w_11` char(1) default NULL,
  `w_12` char(1) default NULL,
  `w_13` char(1) default NULL,
  `w_14` char(1) default NULL,
  `w_15` char(1) default NULL,
  `w_16` char(1) default NULL,
  `w_17` char(1) default NULL,
  `w_18` char(1) default NULL,
  `w_19` char(1) default NULL,
  `w_20` char(1) default NULL,
  `w_21` char(1) default NULL,
  `w_22` char(1) default NULL,
  `w_23` char(1) default NULL,
  `w_24` char(1) default NULL,
  `w_25` char(1) default NULL,
  `w_26` char(1) default NULL,
  `w_27` char(1) default NULL,
  `w_28` char(1) default NULL,
  `w_29` char(1) default NULL,
  `w_30` char(1) default NULL,
  `w_31` char(1) default NULL,
  `w_32` char(1) default NULL,
  `w_33` char(1) default NULL,
  `w_34` char(1) default NULL,
  `w_35` char(1) default NULL,
  `w_36` char(1) default NULL,
  `w_37` char(1) default NULL,
  `w_38` char(1) default NULL,
  `w_39` char(1) default NULL,
  `w_40` char(1) default NULL,
  `w_41` char(1) default NULL,
  `w_42` char(1) default NULL,
  `sciezka` varchar(50) default NULL,
  `foto_a` varchar(50) default NULL,
  `foto_b` varchar(50) default NULL,
  `foto_c` varchar(50) default NULL,
  `foto_d` varchar(50) default NULL,
  `foto_e` varchar(50) default NULL,
  `foto_f` varchar(50) default NULL,
  `foto_g` varchar(50) default NULL,
  `foto_h` varchar(50) default NULL,
  `foto_i` varchar(50) default NULL,
  PRIMARY KEY  (`id_dane`),
  KEY `FK_dane_model` (`id_model`),
  KEY `FK_dane_marka` (`id_marka`),
  KEY `FK_dane_3` USING BTREE (`id_typ`)
) ENGINE=InnoDB DEFAULT CHARSET=latin2 ROW_FORMAT=DYNAMIC AUTO_INCREMENT=1;

-- --------------------------------------------------------

--
-- Struktura tabeli dla  `osobowe_marka`
--

CREATE TABLE `osobowe_marka` (
  `id` int(10) unsigned NOT NULL auto_increment,
  `marka` varchar(10) NOT NULL,
  `ile` int(11) NOT NULL default '0',
  PRIMARY KEY  (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=latin2 ROW_FORMAT=DYNAMIC AUTO_INCREMENT=1;

-- --------------------------------------------------------

--
-- Struktura tabeli dla  `osobowe_model`
--

CREATE TABLE `osobowe_model` (
  `id` int(10) unsigned NOT NULL auto_increment,
  `id_marka` int(10) unsigned NOT NULL,
  `model` varchar(10) NOT NULL,
  `ile` int(11) NOT NULL default '0',
  PRIMARY KEY  (`id`),
  KEY `FK_osobowe_model_marka` (`id_marka`)
) ENGINE=InnoDB DEFAULT CHARSET=latin2 ROW_FORMAT=DYNAMIC AUTO_INCREMENT=1;

-- --------------------------------------------------------

--
-- Struktura tabeli dla  `osobowe_typ`
--

CREATE TABLE `osobowe_typ` (
  `id` int(10) unsigned NOT NULL auto_increment,
  `id_model` int(10) unsigned NOT NULL,
  `id_marka` int(10) unsigned NOT NULL,
  `typ` varchar(10) NOT NULL,
  `ile` smallint(5) unsigned NOT NULL default '0',
  PRIMARY KEY  (`id`),
  KEY `FK_osobowe_typ_model` (`id_model`),
  KEY `FK_osobowe_typ_marka` (`id_marka`)
) ENGINE=InnoDB DEFAULT CHARSET=latin2 ROW_FORMAT=DYNAMIC AUTO_INCREMENT=1;


--
-- Ograniczenia dla tabeli `dane`
--
ALTER TABLE `dane`
  ADD CONSTRAINT `FK_dane_typ` FOREIGN KEY (`id_typ`) REFERENCES `osobowe_typ` (`id`),
  ADD CONSTRAINT `FK_dane_marka` FOREIGN KEY (`id_marka`) REFERENCES `osobowe_marka` (`id`),
  ADD CONSTRAINT `FK_dane_model` FOREIGN KEY (`id_model`) REFERENCES `osobowe_model` (`id`);

--
-- Ograniczenia dla tabeli `osobowe_model`
--
ALTER TABLE `osobowe_model`
  ADD CONSTRAINT `FK_osobowe_model_marka` FOREIGN KEY (`id_marka`) REFERENCES `osobowe_marka` (`id`);

--
-- Ograniczenia dla tabeli `osobowe_typ`
--
ALTER TABLE `osobowe_typ`
  ADD CONSTRAINT `FK_osobowe_typ_model` FOREIGN KEY (`id_model`) REFERENCES `osobowe_model` (`id`),
  ADD CONSTRAINT `FK_osobowe_typ_marka` FOREIGN KEY (`id_marka`) REFERENCES `osobowe_marka` (`id`);
  Forum: Przedszkole · Podgląd postu: #431092 · Odpowiedzi: 10 · Wyświetleń: 1 880


New Posts  Nowe odpowiedzi
No New Posts  Brak nowych odpowiedzi
Hot topic  Popularny temat (Nowe)
No new  Popularny temat (Brak nowych)		 Poll  Sonda (Nowe)
No new votes  Sonda (Brak nowych)
Closed  Zamknięty temat
Moved  Przeniesiony temat
 

RSS Wersja Lo-Fi Aktualny czas: 25.04.2024 - 13:34
Powered By IP.Board © 2024  IPS, Inc.
All changes by PHP.pl Administrators
Hosting zapewnia NQ.pl hosting, trac, svn