Loại bỏ trùng lặp mà không thay đổi thứ tự C++

Trong hướng dẫn này, chúng ta sẽ tìm hiểu cách loại bỏ phần tử trùng lặp khỏi mảng. Trước khi tiếp tục với chương trình, nếu bạn không quen thuộc với Mảng là gì, vui lòng đọc bài viết này. Mảng trong ngôn ngữ C

Xem video này trên YouTube

Một cách khác là sử dụng cách hiểu danh sách

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> [result.append(item) for item in initial if item not in result]
 [None, None, None, None]
 >>> result
 
 [1, 9, 6, 7]

Khả năng hiểu danh sách là các công cụ Python tiện dụng và rất mạnh mẽ cho phép bạn kết hợp các biến, vòng lặp for và câu lệnh if. Chúng cho phép tạo danh sách với một dòng mã (nhưng bạn cũng có thể chia chúng thành nhiều dòng để cải thiện khả năng đọc. )

Mặc dù ngắn hơn và vẫn khá rõ ràng, nhưng sử dụng cách hiểu danh sách trong trường hợp này không phải là một ý kiến ​​hay

Đó là bởi vì nó sử dụng cùng một cách tiếp cận không hiệu quả để kiểm tra tư cách thành viên mà chúng ta đã thấy trong Phương pháp 1. Nó cũng dựa vào các tác dụng phụ của việc hiểu để xây dựng danh sách kết quả, điều mà nhiều người cho là không tốt

Để giải thích thêm, ngay cả khi nó không được gán cho một biến để sử dụng sau này, thì việc hiểu danh sách vẫn tạo ra một đối tượng danh sách. Vì vậy, trong quá trình nối thêm các mục từ danh sách ban đầu vào danh sách

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> for item in initial:
         if item not in result:
             result.append(item)
 >>> result
 
 [1, 9, 6, 7]

5, mã của chúng tôi cũng đang tạo danh sách thứ ba chứa giá trị trả về của mỗi lệnh gọi

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> for item in initial:
         if item not in result:
             result.append(item)
 >>> result
 
 [1, 9, 6, 7]

6

Các hàm Python trả về giá trị

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> for item in initial:
         if item not in result:
             result.append(item)
 >>> result
 
 [1, 9, 6, 7]

7 nếu không có giá trị trả về nào khác được chỉ định, nghĩa là (như bạn có thể thấy ở trên) đầu ra từ danh sách thứ ba là.  

________số 8_______

Vòng lặp for rõ ràng hơn và không phụ thuộc vào tác dụng phụ, vì vậy đây là phương pháp tốt hơn cho cả hai trong trường hợp này

Phương pháp 3 – Tập hợp được sắp xếp

Chúng tôi không thể đơn giản chuyển đổi danh sách của mình thành một bộ để loại bỏ các bản sao nếu chúng tôi muốn giữ trật tự. Tuy nhiên, sử dụng phương pháp này kết hợp với chức năng được sắp xếp là một cách tiềm năng khác về phía trước

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = sorted(set(initial), key=initial.index)
 >>> result
 
 [1, 9, 6, 7]

Như bạn có thể thấy, phương thức này sử dụng chỉ mục của danh sách ban đầu để sắp xếp tập hợp các giá trị duy nhất theo đúng thứ tự

Vấn đề là mặc dù nó khá dễ hiểu nhưng nó không nhanh hơn nhiều so với vòng lặp for cơ bản được trình bày trong Phương pháp 1

Cách 4 – Dictionary fromkeys()

Một cách tiếp cận nhanh chóng nghiêm túc là sử dụng từ điển

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = list(dict.fromkeys(initial))
 >>> result
 
 [1, 9, 6, 7]

Giống như bộ, từ điển sử dụng , có nghĩa là chúng cực kỳ nhanh

Các khóa từ điển Python là duy nhất theo mặc định, vì vậy việc chuyển đổi danh sách của chúng tôi thành từ điển sẽ tự động loại bỏ các bản trùng lặp

Phương thức

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> for item in initial:
         if item not in result:
             result.append(item)
 >>> result
 
 [1, 9, 6, 7]

8 tạo một từ điển mới bằng cách sử dụng các phần tử từ một lần lặp làm khóa.  

Khi điều này đã được thực hiện với danh sách ban đầu của chúng tôi, việc chuyển đổi từ điển trở lại danh sách sẽ cho kết quả mà chúng tôi đang tìm kiếm

Từ điển chỉ được đặt hàng trong tất cả các triển khai python khi Python 3. 7 đã được phát hành (đây cũng là chi tiết triển khai của CPython 3. 6).  

Vì vậy, nếu bạn đang sử dụng phiên bản Python cũ hơn, bạn sẽ cần nhập lớp

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> for item in initial:
         if item not in result:
             result.append(item)
 >>> result
 
 [1, 9, 6, 7]

9 từ gói bộ sưu tập trong thư viện chuẩn để thay thế

 >>> from collections import OrderedDict
 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = list(OrderedDict.fromkeys(initial))
 >>> result
 
 [1, 9, 6, 7]

Cách tiếp cận này có thể không nhanh bằng cách sử dụng từ điển tiêu chuẩn, nhưng nó vẫn rất nhanh

Bài tập. Chạy mã. Nó có hoạt động không?

Phương pháp 5 – more-itertools

Cho đến thời điểm này, chúng tôi chỉ xem xét các danh sách chứa. Nhưng nếu danh sách của bạn chứa các kiểu dữ liệu có thể thay đổi như danh sách, bộ hoặc từ điển thì sao?

Vẫn có thể sử dụng vòng lặp for cơ bản được hiển thị trong Phương pháp 1, nhưng điều đó sẽ không quá khó nếu tốc độ là điều cốt yếu

Ngoài ra, nếu chúng tôi cố gắng sử dụng

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> for item in initial:
         if item not in result:
             result.append(item)
 >>> result
 
 [1, 9, 6, 7]

8, chúng tôi sẽ nhận được một

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> [result.append(item) for item in initial if item not in result]
 [None, None, None, None]
 >>> result
 
 [1, 9, 6, 7]

1 vì các khóa từ điển phải có thể băm được

Một câu trả lời tuyệt vời cho câu hỏi hóc búa này xuất hiện dưới dạng một thư viện có tên more-itertools. Nó không phải là một phần của thư viện chuẩn Python nên bạn sẽ cần cài đặt nó

Khi đã xong, bạn có thể nhập và sử dụng chức năng

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> [result.append(item) for item in initial if item not in result]
 [None, None, None, None]
 >>> result
 
 [1, 9, 6, 7]

2 của nó như vậy

 >>> from more_itertools import unique_everseen
 >>> mutables = [[1, 2, 3], [2, 3, 4], [1, 2, 3]]
 >>> result = list(unique_everseen(mutables))
 >>> result
 
 [[1, 2, 3], [2, 3, 4]]

Thư viện

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> [result.append(item) for item in initial if item not in result]
 [None, None, None, None]
 >>> result
 
 [1, 9, 6, 7]

3 được thiết kế đặc biệt để làm việc với các kiểu dữ liệu có thể lặp lại của Python theo cách hiệu quả (nó bổ sung cho các công cụ lặp là một phần của thư viện chuẩn)

Hàm

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> [result.append(item) for item in initial if item not in result]
 [None, None, None, None]
 >>> result
 
 [1, 9, 6, 7]

2 mang lại các phần tử duy nhất trong khi vẫn giữ nguyên trật tự và đặc biệt là nó có thể xử lý các loại dữ liệu có thể thay đổi, vì vậy, đây chính xác là thứ chúng tôi đang tìm kiếm

Chức năng này cũng cung cấp một cách để loại bỏ các mục trùng lặp nhanh hơn khỏi danh sách các danh sách

 ...
 >>> result = list(unique_everseen(mutables, key=tuple))
 >>> result
 
 [[1, 2, 3], [2, 3, 4]]

Điều này hoạt động tốt vì nó chuyển đổi các danh sách không thể băm thành các bộ có thể băm để tăng tốc mọi thứ hơn nữa

Nếu bạn muốn áp dụng thủ thuật này cho danh sách các bộ, bạn có thể sử dụng freezeset làm khóa

 ...
 >>> mutables = [{1, 2, 3}, {2, 3, 4}, {1, 2, 3}]
 >>> result = list(unique_everseen(mutables, key=frozenset))
 >>> result
 
 [{1, 2, 3}, {2, 3, 4}]

Chỉ định khóa với danh sách từ điển phức tạp hơn một chút nhưng vẫn có thể đạt được với sự trợ giúp của hàm lambda

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> for item in initial:
         if item not in result:
             result.append(item)
 >>> result
 
 [1, 9, 6, 7]

0

Hàm

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> [result.append(item) for item in initial if item not in result]
 [None, None, None, None]
 >>> result
 
 [1, 9, 6, 7]

2 cũng có thể được sử dụng với các danh sách chứa hỗn hợp các mục có thể lặp lại và không thể lặp lại (nghĩ rằng số nguyên và số thực), đây là một phần thưởng thực sự. Cố gắng cung cấp khóa trong trường hợp này sẽ dẫn đến

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> [result.append(item) for item in initial if item not in result]
 [None, None, None, None]
 >>> result
 
 [1, 9, 6, 7]

1 mặc dù

Phương pháp 6 – NumPy duy nhất()

Nếu bạn đang làm việc với dữ liệu số, thư viện bên thứ ba numpy cũng là một tùy chọn

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> for item in initial:
         if item not in result:
             result.append(item)
 >>> result
 
 [1, 9, 6, 7]

1

Giá trị chỉ mục của các mục duy nhất có thể được lưu trữ bằng cách sử dụng hàm

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> [result.append(item) for item in initial if item not in result]
 [None, None, None, None]
 >>> result
 
 [1, 9, 6, 7]

7 với tham số

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> [result.append(item) for item in initial if item not in result]
 [None, None, None, None]
 >>> result
 
 [1, 9, 6, 7]

8 được đặt thành

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> [result.append(item) for item in initial if item not in result]
 [None, None, None, None]
 >>> result
 
 [1, 9, 6, 7]

9

Những thứ này sau đó có thể được chuyển đến

[None, None, None, None]

0 để tạo ra một lát cắt được sắp xếp chính xác với các bản sao đã bị xóa

Về mặt kỹ thuật, phương pháp này có thể được áp dụng cho một danh sách tiêu chuẩn bằng cách trước tiên chuyển đổi nó thành một mảng có nhiều mảng và sau đó chuyển đổi nó trở lại định dạng danh sách ở cuối. Tuy nhiên, đây sẽ là một cách quá phức tạp và không hiệu quả để đạt được kết quả.

Sử dụng các loại kỹ thuật này chỉ thực sự có ý nghĩa nếu bạn cũng đang sử dụng một số tính năng mạnh mẽ của numpy vì những lý do khác

Phương pháp 7 – gấu trúc độc nhất()

Một thư viện bên thứ ba khác mà chúng tôi có thể sử dụng là pandas

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> for item in initial:
         if item not in result:
             result.append(item)
 >>> result
 
 [1, 9, 6, 7]

2

[None, None, None, None]

1 phù hợp hơn với nhiệm vụ vì nó giữ trật tự theo mặc định và

[None, None, None, None]

2 nhanh hơn đáng kể so với

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> [result.append(item) for item in initial if item not in result]
 [None, None, None, None]
 >>> result
 
 [1, 9, 6, 7]

7

Như với phương pháp numpy, hoàn toàn có thể chuyển đổi kết quả thành danh sách tiêu chuẩn ở cuối

Tuy nhiên, một lần nữa, trừ khi bạn đang sử dụng các công cụ phân tích dữ liệu tuyệt vời do gấu trúc cung cấp cho mục đích khác, không có lý do rõ ràng nào để chọn phương pháp này thay vì tùy chọn thậm chí còn nhanh hơn bằng cách sử dụng kiểu dữ liệu từ điển tích hợp sẵn của Python (Phương pháp 4)

Bản tóm tắt

Như chúng ta đã thấy, có rất nhiều cách để giải quyết vấn đề này và quyết định chọn cách nào sẽ tùy thuộc vào hoàn cảnh cụ thể của bạn.  

Nếu bạn đang viết một kịch bản nhanh và danh sách của bạn không nhiều, bạn có thể chọn sử dụng một vòng lặp for đơn giản vì mục đích rõ ràng

Tuy nhiên, nếu tính hiệu quả là một yếu tố và danh sách của bạn không chứa các mục có thể thay đổi thì sử dụng

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> for item in initial:
         if item not in result:
             result.append(item)
 >>> result
 
 [1, 9, 6, 7]

8 là một lựa chọn tuyệt vời. Thật tuyệt khi phương pháp này sử dụng một trong các kiểu dữ liệu tích hợp sẵn của Python và duy trì mức độ dễ đọc tốt trong khi cải thiện đáng kể tốc độ của vòng lặp for

Ngoài ra, nếu bạn đang sử dụng phiên bản Python cũ hơn, thì

[None, None, None, None]

5 là một lựa chọn thực sự tốt vì nó vẫn rất nhanh

Nếu bạn cần làm việc với các danh sách chứa các mục có thể thay đổi, việc nhập more-itertools để bạn có thể tận dụng chức năng tuyệt vời

 >>> initial = [1, 1, 9, 1, 9, 6, 9, 7]
 >>> result = []
 >>> [result.append(item) for item in initial if item not in result]
 [None, None, None, None]
 >>> result
 
 [1, 9, 6, 7]

2 sẽ rất có ý nghĩa

Cuối cùng, nếu bạn đang thực hiện một số thao tác số nghiêm trọng với dữ liệu gọn gàng hoặc thao tác với gấu trúc, thì có lẽ nên sử dụng các phương thức được tích hợp trong các công cụ đó cho mục đích này.  

Tất nhiên, sự lựa chọn là của bạn và tôi hy vọng bài viết này đã cung cấp một số thông tin chi tiết hữu ích giúp bạn chọn được cách tiếp cận phù hợp cho công việc hiện tại

Bạn có thể xóa các bản sao mà không cần chuyển ô không?

Làm cách nào để loại bỏ các bản sao khỏi mảng mà không thay đổi thứ tự?

Làm cách nào để loại bỏ các bản sao trong C?

Loại bỏ trùng lặp có loại bỏ thứ nhất hay thứ hai không?