Trong java ngoài cách duyệt mảng bằng vòng lặp for, for each, while, do while thì còn cách nào không?

#21

chủ thớt sửa dòng này:

Set<String> setInsert = new TreeSet<>();

thành

Set<String> setInsert = new HashSet<>();

xem còn mấy giây, hên xui :joy:

6 Likes
#22

Dữ liệu nhỏ (cả về số lượng lẫn độ dài của 1 element) thì chắc là k thấy khác biệt lắm. Nếu nhìn milis thì chắc mới thấy đc :v

4 Likes
#23

Tớ nghĩ tớ sửa lại câu “TreeSet có lợi thế hơn khi dữ liệu đủ lớn” - nó chỉ hợp lệ với Java 7 trở về trước, khi mà HashSet sử dụng linked list để chứa các node trong từng bucket. Tìm kiếm trên Tree thông thường sẽ tốt hơn trong linked list.

Tớ có check lại implement của HashSet (JDK-8 implementation), nếu số lượng phần tử của 1 bucket nhỏ hơn 8, bucket đó sẽ sử dụng linked list để chứa các node; còn nếu số lượng phần tử của 1 bucket lớn hơn hoặc bằng 8, bucket đó sẽ được chuyển thành Tree (java 8+).
Với implement đó, HashSet nên có performance tốt hơn TreeSet in general (ở Java 8+), khi mà HashSet chỉ cần tìm dữ liệu trong không gian bé hơn TreeSet (chỉ trong 1 bucket nhỏ, nếu hash function đủ tốt để cho bucket đó nhỏ :smiley: - trong TH này, là hash function của String), và có thêm đặc tính tốc độ khi tìm kiếm trên Tree (với các bucket to. Các bucket nhỏ thì tìm kiếm tuần tự trên linked list không có quá nhiều khác biệt).

5 Likes
#24

Dùng HashSet nhanh hơn bác ơi !!! kkk em đã sửa theo bác Huy_Nguyen1 và nhanh hơn thật bác ạ :v em chỉnh TreeSet thành HashSet và thay contain bằng startWith tốc độ chạy đã giảm một nữa bác :v còn tầm 0.2s hơn thôi :v

5 Likes
#25

Ko biết java string hash tốt đến đâu nhưng việc trùng hash với khác input là nhỏ. Với theo bài trên thì phải dùng insert lẫn search. Btw, HashSet dùng equals vẫn có lợi thế hơn TreeSet dùng compareTo nếu độ dài string khác nhau. Với lại thì big O notation vẫn là tham khảo tốt. Còn chắc nhất vẫn là test thử :thinking:

4 Likes
#26

cứ chạy thử code cái nào chạy lẹ hơn thì xài :upside_down_face:

0.57s là nhiều rồi, swap 2 cái chạy thử cái nào lẹ hơn thì xài :kissing:

5 Likes
#27

Em cảm ơn mn đã góp ý cho em ạ, và code hiện tại của em sau khi chỉnh sửa đây ạ chỉ tầm 0.23s thôi ạ. Em cảm ơn mn nhiều lắm ạ.

    static String[] dictionary(String[] arr_op) {

        Set<String> setInsert = new HashSet<>();
        ArrayList<String> result = new ArrayList<>();

        for (int i = 0; i < arr_op.length; i++) {
            if (arr_op[i].startsWith("insert")) {
                setInsert.add(arr_op[i].substring(7));
            } else {
                if (setInsert.contains(arr_op[i].substring(5))) {
                    result.add("yes");
                } else {
                    result.add("no");
                }
            }
        }
             return result.toArray(new String[0]);
    }
2 Likes
#28

Em đổi thêm contain thành startWith và TreeSet thành HashSet nó giảm chỉ còn 0.23 thôi ạ.

#29

đổi lại TreeSet coi lẹ hơn bao nhiêu giây :thinking:

rồi tiết mục đố vui coi arr_op.length có giá trị là bao nhiêu :face_with_monocle:

3 Likes
#30

sài TreeSet mà giữ nguyên contain thì là 0.43s nha bác :v

#31

vậy chắc arr_op.length cỡ 10^5 :smiling_face_with_three_hearts:
có khi 10^6 :joy: chắc 70% là 10^5, hên xui :smiling_face_with_three_hearts:

5 Likes
#32

kk em vừa coi lại tiêu chuẩn đề bài thì đầu vào giới hạn là: 1 ≤ arr_op.size() ≤ 2 x 10^5 ạ

3 Likes
#33

gần đúng :angry: cảm giác 0.2s chênh lệch ko thể chỉ là 10^5 được :sunglasses:

5 Likes
#34

contains là toang nhé :smiley:

5 Likes
#35

Dạ Contain là toang ngay ạ, hôm qua bác kia có đưa cái issue cho em nếu dùng contain rồi ạ.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?