Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite625726

Browse files
feat: added ukr translations for bloom filter, Disjoint Set, Doubly Linked List (trekhleb#957)
Co-authored-by: Oleksii Trekhleb <trehleb@gmail.com>
1 parent5de9ca2 commite625726

File tree

6 files changed

+217
-30
lines changed

6 files changed

+217
-30
lines changed

‎src/data-structures/bloom-filter/README.md

Lines changed: 19 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -2,38 +2,39 @@
22

33
_Read this in other languages:_
44
[_Русский_](README.ru-RU.md),
5-
[_Português_](README.pt-BR.md)
5+
[_Português_](README.pt-BR.md),
6+
[_Українська_](README.uk-UA.md)
67

7-
A**bloom filter** is a space-efficient probabilistic
8-
data structure designed to test whether an element
9-
is present in a set. It is designed to be blazingly
8+
A**bloom filter** is a space-efficient probabilistic
9+
data structure designed to test whether an element
10+
is present in a set. It is designed to be blazingly
1011
fast and use minimal memory at the cost of potential
1112
false positives. False positive matches are possible,
1213
but false negatives are not – in other words, a query
1314
returns either "possibly in set" or "definitely not in set".
1415

15-
Bloom proposed the technique for applications where the
16+
Bloom proposed the technique for applications where the
1617
amount of source data would require an impractically large
17-
amount of memory if "conventional" error-free hashing
18+
amount of memory if "conventional" error-free hashing
1819
techniques were applied.
1920

2021
##Algorithm description
2122

22-
An empty Bloom filter is a bit array of`m` bits, all
23+
An empty Bloom filter is a bit array of`m` bits, all
2324
set to`0`. There must also be`k` different hash functions
24-
defined, each of which maps or hashes some set element to
25-
one of the`m` array positions, generating a uniform random
26-
distribution. Typically,`k` is a constant, much smaller
27-
than`m`, which is proportional to the number of elements
28-
to be added; the precise choice of`k` and the constant of
29-
proportionality of`m` are determined by the intended
25+
defined, each of which maps or hashes some set element to
26+
one of the`m` array positions, generating a uniform random
27+
distribution. Typically,`k` is a constant, much smaller
28+
than`m`, which is proportional to the number of elements
29+
to be added; the precise choice of`k` and the constant of
30+
proportionality of`m` are determined by the intended
3031
false positive rate of the filter.
3132

32-
Here is an example of a Bloom filter, representing the
33-
set`{x, y, z}`. The colored arrows show the positions
34-
in the bit array that each set element is mapped to. The
35-
element`w` is not in the set`{x, y, z}`, because it
36-
hashes to one bit-array position containing`0`. For
33+
Here is an example of a Bloom filter, representing the
34+
set`{x, y, z}`. The colored arrows show the positions
35+
in the bit array that each set element is mapped to. The
36+
element`w` is not in the set`{x, y, z}`, because it
37+
hashes to one bit-array position containing`0`. For
3738
this figure,`m = 18` and`k = 3`.
3839

3940
![Bloom Filter](https://upload.wikimedia.org/wikipedia/commons/a/ac/Bloom_filter.svg)
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
#Фільтр Блума
2+
3+
**Фільтр Блума** - це просторово-ефективна ймовірна структура даних, створена для перевірки наявності елемента
4+
у множині. Він спроектований неймовірно швидким за мінімального використання пам'яті ціною потенційних помилкових спрацьовувань.
5+
Існує можливість отримати хибнопозитивне спрацьовування (елемента в безлічі немає, але структура даних повідомляє,
6+
що він є), але не хибнонегативне. Іншими словами, черга повертає або "можливо в наборі", або "певно не
7+
у наборі". Фільтр Блума може використовувати будь-який обсяг пам'яті, проте чим він більший, тим менша вірогідність помилкового
8+
спрацьовування.
9+
10+
Блум запропонував цю техніку для застосування в областях, де кількість вихідних даних потребувала б непрактично багато
11+
пам'яті, у разі застосування умовно безпомилкових технік хешування.
12+
13+
##Опис алгоритму
14+
15+
Порожній фільтр Блума представлений бітовим масивом з`m` бітів, всі біти якого обнулені. Має бути визначено`k`
16+
незалежних хеш-функцій, що відображають кожен елемент множини в одну з`m` позицій у масиві, генеруючи однакове
17+
випадковий розподіл. Зазвичай`k` задана константою, яка набагато менше`m` і пропорційна
18+
кількості елементів, що додаються; точний вибір`k` та постійної пропорційності`m` визначаються рівнем хибних
19+
спрацьовувань фільтра.
20+
21+
Ось приклад Блум фільтра, що представляє набір`{x, y, z}`. Кольорові стрілки показують позиції в бітовому масиві,
22+
яким прив'язаний кожен елемент набору. Елемент`w` не в наборі`{x, y, z}`, тому що він прив'язаний до позиції в бітовому
23+
масиві, що дорівнює`0`. Для цієї форми,`m = 18`, а`k = 3`.
24+
25+
Фільтр Блума є бітовий масив з`m` біт. Спочатку, коли структура даних зберігає порожню множину, всі
26+
m біт обнулені. Користувач повинен визначити`k` незалежних хеш-функцій`h1`, …,`hk`,
27+
що відображають кожен елемент в одну з m позицій бітового масиву досить рівномірним чином.
28+
29+
Для додавання елемента e необхідно записати одиниці на кожну з позицій`h1(e)`, …,`hk(e)`
30+
бітового масиву.
31+
32+
Для перевірки приналежності елемента`e` до безлічі елементів, що зберігаються, необхідно перевірити стан бітів
33+
`h1(e)`, …,`hk(e)`. Якщо хоча б один з них дорівнює нулю, елемент не може належати множині
34+
(інакше при його додаванні всі ці біти були встановлені). Якщо вони рівні одиниці, то структура даних повідомляє,
35+
що`е` належить безлічі. При цьому може виникнути дві ситуації: або елемент дійсно належить множині,
36+
або всі ці біти виявилися встановлені випадково при додаванні інших елементів, що і є джерелом помилкових
37+
спрацьовувань у цій структурі даних.
38+
39+
![Фільтр Блума](https://upload.wikimedia.org/wikipedia/commons/a/ac/Bloom_filter.svg)
40+
41+
##Застосування
42+
43+
Фільтр Блума може бути використаний для блогів. Якщо мета полягає в тому, щоб показати читачам лише ті статті,
44+
які вони ще не бачили, фільтр блуму ідеальний. Він може містити значення, що хешуються, відповідні статті. Після
45+
того, як користувач прочитав кілька статей, вони можуть бути поміщені у фільтр. Наступного разу, коли користувач
46+
відвідає сайт, ці статті можуть бути вилучені з результатів за допомогою фільтра.
47+
48+
Деякі статті неминуче будуть відфільтровані помилково, але ціна прийнятна. Те, що користувач не побачить дещо
49+
статей цілком прийнятно, беручи до уваги той факт, що йому завжди показуються інші нові статті при кожному
50+
новому відвідуванні.
51+
52+
##Посилання
53+
54+
-[Wikipedia](https://uk.wikipedia.org/wiki/%D0%A4%D1%96%D0%BB%D1%8C%D1%82%D1%80_%D0%91%D0%BB%D1%83%D0%BC%D0%B0)

‎src/data-structures/disjoint-set/README.md

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -2,22 +2,22 @@
22

33
_Read this in other languages:_
44
[_Русский_](README.ru-RU.md),
5-
[_Português_](README.pt-BR.md)
5+
[_Português_](README.pt-BR.md),
6+
[_Українська_](README.uk-UA.md)
67

7-
8-
**Disjoint-set** data structure (also called a union–find data structure or merge–find set) is a data
9-
structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
10-
It provides near-constant-time operations (bounded by the inverse Ackermann function) to*add new sets*,
11-
to*merge existing sets*, and to*determine whether elements are in the same set*.
8+
**Disjoint-set** data structure (also called a union–find data structure or merge–find set) is a data
9+
structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets.
10+
It provides near-constant-time operations (bounded by the inverse Ackermann function) to_add new sets_,
11+
to_merge existing sets_, and to_determine whether elements are in the same set_.
1212
In addition to many other uses (see the Applications section), disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph.
1313

1414
![disjoint set](https://upload.wikimedia.org/wikipedia/commons/6/67/Dsu_disjoint_sets_init.svg)
1515

16-
*MakeSet* creates 8 singletons.
16+
_MakeSet_ creates 8 singletons.
1717

1818
![disjoint set](https://upload.wikimedia.org/wikipedia/commons/a/ac/Dsu_disjoint_sets_final.svg)
1919

20-
After some operations of*Union*, some sets are grouped together.
20+
After some operations of_Union_, some sets are grouped together.
2121

2222
##References
2323

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
#Система неперетинних множин
2+
3+
**Система неперетинних множин** це структура даних (також звана структурою даної пошуку перетину або
4+
безліччю пошуку злиття), яка управляє безліччю елементів, розбитих на кілька підмножин, що не перетинаються.
5+
Вона надає близько-константний час виконання операцій (обмежений зворотною функцією Акерманна) за додаванням
6+
нових множин,*злиття існуючих множин і*випередження, чи відносяться елементи до одного і того ж безлічі.
7+
8+
Застосовується для зберігання компонентів зв'язності в графах, зокрема, алгоритму Фарбала необхідна подібна структура
9+
даних для ефективної реалізації.
10+
11+
Основні операції:
12+
13+
-_MakeSet(x)_ - створює одноелементне безліч {x},
14+
-_Find(x)_ - повертає ідентифікатор множини, що містить елемент x,
15+
-_Union(x,y)_ - об'єднання множин, що містять x та y.
16+
17+
Після деяких операцій_об'єднання_, деякі множини зібрані разом
18+
19+
##Посилання
20+
21+
-[СНМ на Wikipedia](https://uk.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%BD%D0%B5%D0%BF%D0%B5%D1%80%D0%B5%D1%82%D0%B8%D0%BD%D0%BD%D0%B8%D1%85_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B8%D0%BD)
22+
-[СНМ на YouTube](https://www.youtube.com/watch?v=5XwRPwLnK6I)

‎src/data-structures/doubly-linked-list/README.md

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@ _Read this in other languages:_
77
[_Português_](README.pt-BR.md),
88
[_한국어_](README.ko-KR.md),
99
[_Español_](README.es-ES.md),
10+
[_Українська_](README.uk-UA.md)
1011

1112
In computer science, a**doubly linked list** is a linked data structure that
1213
consists of a set of sequentially linked records called nodes. Each node contains
@@ -20,7 +21,7 @@ but in opposite sequential orders.
2021

2122
![Doubly Linked List](./images/doubly-linked-list.jpeg)
2223

23-
*Made with[okso.app](https://okso.app)*
24+
_Made with[okso.app](https://okso.app)_
2425

2526
The two node links allow traversal of the list in either direction. While adding
2627
or removing a node in a doubly linked list requires changing more links than the
@@ -104,9 +105,9 @@ end Reverse Traversal
104105

105106
##Time Complexity
106107

107-
| Access| Search| Insertion| Deletion|
108-
| :-------:| :-------:| :-------:| :-------:|
109-
| O(n)|O(n)|O(1)| O(n)|
108+
| Access| Search| Insertion| Deletion|
109+
| :----:| :----:| :-------:| :------:|
110+
|O(n)|O(n)| O(1)| O(n)|
110111

111112
###Space Complexity
112113

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
#Двобічно зв'язаний список
2+
3+
**Двобічно зв'язаний список** — зв'язкова структура даних в інформатиці, що складається з набору
4+
послідовно пов'язаних записів, званих вузлами. Кожен вузол містить два поля,
5+
званих посиланнями, які вказують на попередній і наступний елементи
6+
послідовність вузлів. Посилання на попередній елемент кореневого вузла та посилання на
7+
Наступний елемент останнього вузла вказують на деякого роду переривник, зазвичай
8+
сторожовий вузол або null для полегшення обходу списку. Якщо у списку лише один
9+
сторожовий вузол, тоді перелік циклічно пов'язаний через нього.
10+
Двобічно зв'язаний список можна уявити, як два зв'язкові списки, які утворені з
11+
одних і тих самих даних, але розташованих у протилежному порядку.
12+
13+
![Двобічно зв'язаний список](./images/doubly-linked-list.jpeg)
14+
15+
_Made with[okso.app](https://okso.app)_
16+
17+
Два посилання дозволяють обходити список в обох напрямках. Додавання та
18+
видалення вузла у двозв'язному списку вимагає зміни більшої кількості посилань,
19+
ніж аналогічні операції у зв'язковому списку. Однак дані операції простіше та потенційно
20+
більш ефективні (для некореневих вузлів) – при обході не потрібно стежити за попереднім
21+
вузлом або повторно обходити список у пошуку попереднього вузла, плюс його посилання
22+
може бути змінено.
23+
24+
##Псевдокод основних операцій
25+
26+
###Вставка
27+
28+
```text
29+
Add(value)
30+
Pre: value - значення, що додається
31+
Post: value поміщено в кінець списку
32+
n ← node(value)
33+
if head = ø
34+
head ← n
35+
tail ← n
36+
else
37+
n.previous ← tail
38+
tail.next ← n
39+
tail ← n
40+
end if
41+
end Add
42+
```
43+
44+
###Видалення
45+
46+
```text
47+
Remove(head, value)
48+
Pre: head - перший вузол у списку
49+
value - значення, яке слід видалити
50+
Post: true - value видалено зі списку, інакше false
51+
if head = ø
52+
return false
53+
end if
54+
if value = head.value
55+
if head = tail
56+
head ← ø
57+
tail ← ø
58+
else
59+
head ← head.next
60+
head.previous ← ø
61+
end if
62+
return true
63+
end if
64+
n ← head.next
65+
while n = ø and value = n.value
66+
n ← n.next
67+
end while
68+
if n = tail
69+
tail ← tail.previous
70+
tail.next ← ø
71+
return true
72+
else if n = ø
73+
n.previous.next ← n.next
74+
n.next.previous ← n.previous
75+
return true
76+
end if
77+
return false
78+
end Remove
79+
```
80+
81+
###Зворотний обхід
82+
83+
```text
84+
ReverseTraversal(tail)
85+
Pre: tail - кінцевий елемент обхідного списку
86+
Post: елементи списку пройдено у зворотному порядку
87+
n ← tail
88+
while n = ø
89+
yield n.value
90+
n ← n.previous
91+
end while
92+
end Reverse Traversal
93+
```
94+
95+
##Складність
96+
97+
##Часова складність
98+
99+
| Читання| Пошук| Вставка| Видалення|
100+
| :-----:| :---:| :-----:| :-------:|
101+
| O(n)| O(n)| O(1)| O(n)|
102+
103+
###Просторова складність
104+
105+
O(n)
106+
107+
##Посилання
108+
109+
-[Wikipedia](https://uk.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B1%D1%96%D1%87%D0%BD%D0%BE_%D0%B7%D0%B2%27%D1%8F%D0%B7%D0%B0%D0%BD%D0%B8%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA#:~:text=%D0%94%D0%B2%D0%BE%D0%B1%D1%96%D1%87%D0%BD%D0%BE%20%D0%B7%D0%B2'%D1%8F%D0%B7%D0%B0%D0%BD%D0%B8%D0%B9%20%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA%20%E2%80%94%20%D0%B2%D0%B8%D0%B4,%D0%BD%D0%B0%20%D0%BF%D0%BE%D0%B4%D0%B0%D0%BB%D1%8C%D1%88%D0%B8%D0%B9%20%D0%B2%D1%83%D0%B7%D0%BE%D0%BB%20%D1%83%20%D1%81%D0%BF%D0%B8%D1%81%D0%BA%D1%83.)

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp