In ra lần lượt các số trong dãy số mà chỉ xuất hiện đúng một lần, theo thứ tự xuất hiện

[tntxtnt]

thế Python ko có tree map thì ko tìm phần tử xuất hiện nhiều nhất được à? Xài dict là hash map ngon lành đó thôi?

ví dụ 100k từ chỉ có 1k từ khác biệt, bỏ vào hasp map còn 1k entry, rồi lại sợ ko duyệt qua hash map mà đi xài sort hay tree map à? :V

ví dụ cái hash map như thế này

         pe
pb  [0]: 1 -> 2 -> null
    [1]: null
    [2]: null
    [3]: 9 -> 7 -> null
    [4]: null
    null

thì để duyệt phần tử tiếp theo của pe chỉ cần code thế này

if (pe) pe = pe->next;
while (!pe)
{
    pb = pb->next;
    if (pb) pe = pb->pElement; else break;
}

thì “ko nên duyệt qua hash map” là tại sao, nó có tốn bao nhiêu đâu? Tốn O(n + m) trong đó m là số bucket, nhưng m ~ n nên cũng là O(n), sợ gì mà ko duyệt :V

[Red_Sand (mondlicht1)]

unodered map với dict chắc chắn không dùng hashing with chaining, nhiều khả năng là perfect hashing + universal. Mỗi lần table resize, nó nhân đôi size. Nếu n keys hash vào 1 slot, hash table con có size n^2, thì duyệt qua chẳng phải ý hay.
Ngay cả chaning hash table như bạn viết ở trên, vẫn phải duyệt qua O(n) slot. Cái hash table đó sẽ ok hơn rất nhiều nếu chỉ để lưu số lần xuất hiện của từ, tức rank trên tree, rồi update từ đó trên tree theo rank.
Lúc tìm từ xuất hiện 7 lần chẳng hạn, duyệt tree O(log n) time chẳng phải hiệu quả hơn?
Mỗi ctdl có 1 thế mạnh, mình chưa thấy ai dùng hash map để “duyệt” cả

[tntxtnt]

Mỗi lần table resize, nó nhân đôi size. Nếu n keys hash vào 1 slot, hash table con có size n^2, thì duyệt qua chẳng phải ý hay.

bucket size m với element size n nó có tỉ lệ nhất định gọi là từ gì đó quên rồi, nhưng ở trong Java hash map thì n / m = 0.75, nghĩa là m lúc nào cũng cỡ c*n với c là hằng số, làm gì lên tới n^2 được :V

Ngay cả chaning hash table như bạn viết ở trên, vẫn phải duyệt qua O(n) slot. Cái hash table đó sẽ ok hơn rất nhiều nếu chỉ để lưu số lần xuất hiện của từ, tức rank trên tree, rồi update từ đó trên tree theo rank.
Lúc tìm từ xuất hiện 7 lần chẳng hạn, duyệt tree O(log n) time chẳng phải hiệu quả hơn?

tìm từ xuất hiện 7 lần trên tree map làm gì mà O(logn)? Chẳng phải cũng duyệt qua tất cả các phần tử trên tree map hay sao? Vậy cũng là O(n) chứ :V

“a”: 7
“an”: 3
“the”: 5
…

thì phải duyệt qua hết tất cả các từ trong map mới biết chứ từ nào xuất hiện đúng 7 lần chứ sao lại O(logn) được? :V Chuyển ngược lại thành map<value, keys> à? Thế thì cũng phải duyệt O(n) lần để chuyển ngược lại?

Mỗi ctdl có 1 thế mạnh, mình chưa thấy ai dùng hash map để “duyệt” cả

cho cái ví dụ tìm từ xuất hiện nhiều nhất phải duyệt hash map đó lại bảo chưa thấy ai dùng? :V

đâu có ai nói dùng hash map để duyệt qua tất cả các phần tử trong hmap đâu, chỉ nói là hash map khi cần duyệt tất cả thì cứ duyệt tất cả, tội gì phải tránh :V

[Red_Sand (mondlicht1)]

Ví dụ “văn bản” có 1000 tỉ từ. Lưu vào từ điển là 100 tỉ từ trong từ điển. Rank chắc chắn sẽ có từ trùng rank, nhưng thôi cứ cho là 100 tỉ rank đi. Rồi mỗi lần khách hàng yêu cầu xem từ nào xuất hiện 7 lần, bạn duyệt 100.000.000.000 bước, hay duyệt 36 bước?

Mình nói dùng tree, chứ không phải std map, vì còn tuỳ mục đích mà mỗi tree có optimize khác nhau. Riêng cái tree std map này mình chưa đọc kỹ, xin không dám phán là dùng nó.

bucket size m với element size n nó có tỉ lệ nhất định gọi là từ gì đó quên rồi, nhưng ở trong Java hash map thì n / m = 0.75, nghĩa là m lúc nào cũng cỡ c*n với c là hằng số, làm gì lên tới n^2 được :V

Secondary hash table phải có size n^2 để tránh 2 key bị hash vào cùng 1 slot, đọc birthday paradox.

[tntxtnt]

tra ~c bước :V tính hash value từ đó rồi truy tới bucket chứa nó: hash value % bucket size, rồi mò trong bucket đó từ đúng với từ cần tra thôi?

100 tỉ từ, cho bucket là 150 tỉ bucket đi. Vậy thì trung bình 1 bucket có ~0.67 từ. Xui thì 2 từ trong 1 bucket. Xui nữa thì 10 từ hay 100 từ, thì c tệ nhất là 10-100. Còn 1 bucket có 1 tỉ từ trong đó thì hash function dỏm rồi :V

tree map thì std::map hình như sử dụng red-black tree gì đó, nói chung nó phức tạp hơn hash map nữa nhưng người ta cũng đảm bảo duyệt qua map cũng chỉ tốn O(n) chứ ko phải O(nlogn). Duyệt qua container nào (vector, list, deque, map, set, unordred_map, unordered_set, multimap, multiset, v.v…) cũng tốn O(n) hết, sao lại phải tránh duyệt qua tất cả :V

viết thêm cái: có 1 cái ngôn ngữ rất dzui là Lua, chỉ có 1 container duy nhất là hash table :V Vậy trong Lua phải tránh duyệt “mảng” luôn à :V

[Red_Sand (mondlicht1)]

Xin lỗi, là “từ nào xuất hiện x lần”, không phải “từ này xuất hiện mấy lần”, mình viết lộn.
Mà còn một cách tốt hơn là dùng 2 hash table, một table dùng để lưu số lần xuất hiện, rồi một table dùng số lần xuất hiện làm key, lưu các từ xuất hiện x lần vào container h(x). Việc này sẽ xong trong 1 lần duyệt mảng, với vài thao tác thêm + hash + delete. Hoặc cũng có thể duyệt hash map 1 để build hash map 2, nhưng không bắt buộc, và cũng không phải là điểm “critical” của cách này, Giờ thì có thể search O(1) time luôn. Nhưng nhiều chức năng thiên về so sánh hơn thì cách này không còn tốt bằng tree nữa.
Ví dụ “tìm từ xuất hiện nhiều nhất, hoặc nhiều thứ 100327” thì hash map chậm, nhưng tree thì chỉ cần vài bước duyệt là xong
P/s: Search trong tree là O(log n) nhé.

Lua để viết script. Build software mình sẽ không chọn lua, nên chắc là 1 ngày nào đó phải duyệt qua hash table trong lua thì khó xảy ra.
Ngay cả trong #1, đề bài cũng yêu cầu duyệt theo thứ tự, chẳng người ra đề nào thích ra cái đề “duyệt qua hash map” cả.