1 Тема від dot Востаннє редагувалося dot (15.09.2022 15:16:08)

  • dot
  • dot
  • Replace Group
  • Поза форумом
  • Дата реєстрації: 02.09.2017
  • Повідомлень: 934
    • Репутація: 488

Тема: Optimizatsija pošuku [perevernutyx] slôv vô spystsê

▼Kod
import re, bisect

words = list()

with open("wordlist_20220914175309.csv") as file:  # read, clear, filter file
    for line in file:
        line = re.findall(r"\"([^\"]*)\"", line)[0]
        if (  # do not add if:
            len(line) < 2  # one letter word
            or re.search(r"[^а-щьюяґєії]", line)  # non-ukrainian symbols and unpossible apostrophe in reverse
            or re.search(r"ь[^дтзсцлн]", line)  # unpossible soft-sign in reverse
            or re.search(r"[^аяеєиуюіїо]ï", line)  # želexivka
        ):
            continue
        words.append(line)


def find(elem, words):
    i = bisect.bisect_left(words, elem)
    return i if i != len(words) and words[i] == elem else -1


words.sort()
length = len(words)
index = 0
f = open("result.txt", "w")

while index < length - 1:
    current = words[index]
    result = find(current[::-1], words[index + 1 :])
    if result > -1:
        print(current, current[::-1], file=f)
        del words[index + 1 + result]
        length -= 1
    print(index, length, sep=" / ")
    index += 1

f.close()

Fajl wordlist_<data>.csv zhenerovanyj z Graka (tšy je alternativa, aby tež bralo takož vôdmênky: rik → roku, bo tut je problemy¹) i maje taku strukturu: "<slovo>",<tšyslo>, de <slovo> tse budj-jake slovo, a <tšyslo> — budj-jake tšyslo (tšastota slova, ale tse nevažlyvo tut). Filteruju, aby slovo i perevernute tež vêdpovêdalo sutšasnym normam. Peretvorjuju tse v spysok slôv — tut tse ponad 1 mln (tak, tse dofiga) — i sortuju. Vsji poperednji dêjstva berutj desj v mežax xvylyn/y, tobto ne tak dovho i znov nevažlyvo. Hadaju, zadatša vže vôdnosno otševydna: znajty vsji slova, kotri majutj vôdpovêdnoho «zvorotnjoho» slova: tak — kat, udar — radu itd.

Druha tšasyna je najholovnêšoju. Vykorystovuju pošuk za takoju poradoju. Skorotšuju pošuk v mežax: vôd šukanoho slova do kôntsja; znajdene prybyraju. Tomu tšym blyžtše do kôntsja, tym švydše za logikoju.

Otševydno, možna prybraty print(index, length, sep=" / "), aby robylo štše švydše, tse bulo dlja peršoho zabêhu. Zalyšav na nôtš — desj na 8 hodyn — i vyjšlo desj 321 126 / 1 115 094, tobto majže ⅓. Tož, prosto tsêkavo, tšy možna štše pryšvydšyty?: pokraštšyty filter, pošuk itd.

▼Prymêtky

  1. Sered slôv trapjajutj sja slova z: hynšyx mov, starym pravopysom, abrevijatur itd. Jak tse prybraty tam ž — poky ne znajšov.

dot вебсайт

2 Відповідь від frz

  • frz
  • frz
  • Data / DB Engineer
  • Поза форумом
  • Звідки: PL
  • Дата реєстрації: 28.12.2019
  • Повідомлень: 6 813

Re: Optimizatsija pošuku [perevernutyx] slôv vô spystsê

GPT-4 написав:

Код, наведений вище, відкриває файл "wordlist_20220914175309.csv", зчитує його вміст, фільтрує, сортує й зберігає слова у списку words. За допомогою двійкового пошуку, код знаходить слова, які мають "зворотні" слова (наприклад, "так" - "кат"), і друкує їх у файлі "result.txt".

На даний момент, прискорити алгоритм можна, наприклад, використовуючи такі підходи:

Видаліть зайві виводи, такі як print(index, length, sep=" / "), для зменшення непотрібних операцій.
Використовуйте алгоритми на основі хешування, такі як використання множини для пошуку зворотніх слів замість двійкового пошуку.
Спробуйте використовувати більш ефективні структури даних, такі як хеш-таблиці, які можуть прискорити пошук у великій кількості даних.
Нижче наведений код з деякими пропонованими оптимізаціями:

import re

words = set()

with open("wordlist_20220914175309.csv") as file:
    for line in file:
        line = re.findall(r"\"([^\"]*)\"", line)[0]
        if (
            len(line) < 2
            or re.search(r"[^а-щьюяґєії]", line)
            or re.search(r"ь[^дтзсцлн]", line)
            or re.search(r"[^аяеєиуюіїо]ï", line)
        ):
            continue
        words.add(line)

reversed_words = {word[::-1] for word in words}
result = words.intersection(reversed_words)

with open("result.txt", "w") as f:
    for word in result:
        print(word, word[::-1], file=f)

Цей код використовує множини замість списків для зберігання слів та зворотніх слів, а також використовує перетин множин для знаходження співпадінь.

frz вебсайт