programming python

Viết chương trình python để đếm các ký tự lặp lại và không lặp lại trong một chuỗi

Để tìm ký tự trùng lặp từ chuỗi, chúng ta đếm số lần xuất hiện của từng ký tự trong chuỗi. Nếu số lượng lớn hơn 1, điều đó có nghĩa là một ký tự có một mục nhập trùng lặp trong chuỗi. Trong ví dụ trên, các ký tự được tô màu xanh lục là các ký tự trùng lặp

Trong hướng dẫn này, chúng ta sẽ học cách đếm số lần xuất hiện của một ký tự đã cho trong một chuỗi bằng Python. Chúng tôi sẽ sử dụng từ điển python và cố gắng giải quyết một số vấn đề dựa trên chuỗi. Ta sẽ tìm các ký tự riêng biệt, ký tự rời rạc, ký tự duy nhất của chuỗi và đồng thời đếm số từ có trong chuỗi

Đếm số lần xuất hiện của một ký tự đã cho trong Chuỗi trong Python

string = 'Python Programming'
dictionary = {}
for char in string:
    if[ char in dictionary.keys[]]:
        dictionary[char] += 1
    else:
        dictionary[char]=1
for char in dictionary:
    print[char,' -> ',dictionary[char]]

đầu ra

P -> 2
y -> 1
t -> 1
h -> 1
o -> 2
n -> 2
  -> 1
r -> 2
g -> 2
a -> 1
m -> 2
i -> 1
  • Hãy xem xét một chuỗi [ví dụ. 'Lập trình Python'] và tạo một từ điển trống
  • Sử dụng các ký tự trong chuỗi làm khóa và số lượng của chúng làm giá trị
  • Đối với mọi ký tự trong chuỗi, nếu một ký tự có trong từ điển dưới dạng khóa, hãy tăng giá trị tương ứng của nó. Khác thêm ký tự mới vào từ điển làm khóa và gán giá trị đếm của nó là một

Vì vậy, bây giờ, chúng tôi đã tạo một từ điển python chứa thông tin về chuỗi. Hãy xem những gì chúng ta có thể làm bằng cách sử dụng thông tin này

Vì tôi "không có gì tốt hơn để làm" [hiểu. Tôi có rất nhiều công việc], tôi quyết định tổ chức một cuộc thi biểu diễn nhỏ. Tôi đã tập hợp những câu trả lời hợp lý hoặc thú vị nhất và thực hiện một số 

>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
8 đơn giản bằng Python 3. 5. 1 trên chúng. Tôi đã kiểm tra chúng chỉ với một chuỗi, đây là đầu vào điển hình trong trường hợp của tôi

>>> s = 'ZDXMZKMXFDKXZFKZ'
>>> len[s]
16

Xin lưu ý rằng kết quả có thể khác nhau đối với các đầu vào khác nhau, có thể là độ dài khác nhau của chuỗi hoặc số lượng ký tự riêng biệt khác nhau hoặc số lần xuất hiện trung bình khác nhau trên mỗi ký tự

Đừng phát minh lại bánh xe

Python đã làm cho nó trở nên đơn giản đối với chúng tôi. Lớp 

>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
9 thực hiện chính xác những gì chúng tôi muốn và hơn thế nữa. Cách sử dụng của nó cho đến nay là đơn giản nhất trong tất cả các phương pháp được đề cập ở đây

lấy từ @oefe, rất hay

>>> timeit['Counter[s]', globals=locals[]]
8.208566107001388


>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
0 đi thêm một dặm, đó là lý do tại sao phải mất nhiều thời gian như vậy

¿Từ điển, comprende?

Thay vào đó, hãy thử sử dụng một 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
1 đơn giản. Đầu tiên, hãy làm điều đó một cách khai báo, sử dụng tính năng đọc chính tả

Tôi đã nghĩ ra điều này bản thân mình

________số 8_______

Điều này sẽ trải qua 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
2 từ đầu đến cuối và đối với mỗi ký tự, nó sẽ đếm số lần xuất hiện của nó trong 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
2. Vì 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
2 chứa các ký tự trùng lặp nên phương pháp trên tìm kiếm 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
2 nhiều lần cho cùng một ký tự. Kết quả tự nhiên luôn giống nhau. Vì vậy, hãy đếm số lần xuất hiện chỉ một lần cho mỗi ký tự

Tôi đã tự mình nghĩ ra điều này và @IrshadBhat cũng vậy

>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232

Tốt hơn. Nhưng chúng ta vẫn phải tìm kiếm trong chuỗi để đếm số lần xuất hiện. Một lần tìm kiếm cho từng ký tự riêng biệt. Điều đó có nghĩa là chúng ta sẽ đọc chuỗi nhiều lần. Chúng ta có thể làm tốt hơn thế. Nhưng để làm được điều đó, chúng ta phải từ bỏ con ngựa cao theo chủ nghĩa tuyên bố của mình và đi vào một tư duy mệnh lệnh

mã đặc biệt

AKA Gotta bắt tất cả

lấy cảm hứng từ @anthony

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957

Chà, nó đáng để thử. Nếu bạn đào sâu vào mã nguồn của Python [tôi không thể nói chắc chắn vì tôi chưa bao giờ thực sự làm điều đó], bạn có thể sẽ thấy rằng khi bạn thực hiện 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
6, Python phải kiểm tra xem ngoại lệ được đưa ra có thực sự là của 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
7 hay một số loại khác. Để xem cái quái gì vậy, hãy xem sẽ mất bao lâu nếu chúng ta bỏ qua phần kiểm tra đó và bắt tất cả các ngoại lệ

thực hiện bởi @anthony

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except:
..     d[c] = 1
.. ''', globals=locals[]]
3.3506563019982423

Nó tiết kiệm thời gian, vì vậy người ta có thể muốn sử dụng nó như một cách tối ưu hóa
đừng làm thế. Hoặc thực sự làm. Làm ngay bây giờ

KẾT LUẬN 1

import time
while True:
  try:
    time.sleep[1]
  except:
    print["You're trapped in your own trap!"]

Bạn thấy không? . Trên thực tế, nó bắt được tất cả các ngoại lệ có. Bao gồm cả những thứ mà bạn có thể chưa từng nghe đến, như 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
9

KẾT LUẬN 2

import sys
try:
  print["Goodbye. I'm going to die soon."]
  sys.exit[]
except:
  print['BACK FROM THE DEAD!!!']

Bây giờ quay lại đếm các chữ cái và số và các ký tự khác

Chơi đuổi bắt

Ngoại lệ không phải là cách để đi. Bạn phải cố gắng rất nhiều để bắt kịp họ, và cuối cùng khi bạn làm được, họ chỉ việc lao vào bạn rồi nhướng mày như thể đó là lỗi của bạn. May mắn thay, những người bạn dũng cảm đã mở đường cho chúng tôi để chúng tôi có thể loại bỏ các ngoại lệ, ít nhất là trong bài tập nhỏ này

Lớp 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
1 có một phương thức hay – 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except:
..     d[c] = 1
.. ''', globals=locals[]]
3.3506563019982423
1 – cho phép chúng tôi truy xuất một mục từ từ điển, giống như 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except:
..     d[c] = 1
.. ''', globals=locals[]]
3.3506563019982423
2. Ngoại trừ khi khóa 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except:
..     d[c] = 1
.. ''', globals=locals[]]
3.3506563019982423
3 không có trong từ điển, nó có thể trả về giá trị mặc định. Hãy sử dụng phương pháp đó thay vì loay hoay với các ngoại lệ

tín dụng chuyển đến @Usman

>>> timeit['''
.. d = {}
.. for c in s:
..   d[c] = d.get[c, 0] + 1
.. ''', globals=locals[]]
3.2133633289995487

Gần như nhanh như khả năng hiểu chính tả dựa trên tập hợp. Trên các đầu vào lớn hơn, cái này có thể sẽ còn nhanh hơn nữa

Sử dụng các công cụ thích hợp cho công việc

Đối với lập trình viên Python có kiến ​​thức ít nhất ở mức độ vừa phải, điều đầu tiên xuất hiện trong đầu có lẽ là 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except:
..     d[c] = 1
.. ''', globals=locals[]]
3.3506563019982423
4. Nó thực hiện khá nhiều điều giống như phiên bản ở trên, ngoại trừ thay vì một giá trị, bạn cung cấp cho nó một nhà máy giá trị. Điều đó có thể gây ra một số chi phí, vì giá trị phải được "xây dựng" cho từng khóa bị thiếu riêng lẻ. Hãy xem nó hoạt động như thế nào

hy vọng @AlexMartelli sẽ không đóng đinh tôi vì 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except:
..     d[c] = 1
.. ''', globals=locals[]]
3.3506563019982423
5

>>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613

Không tệ lắm. Tôi muốn nói rằng việc tăng thời gian thực hiện là một khoản thuế nhỏ phải trả cho khả năng đọc được cải thiện. Tuy nhiên, chúng tôi cũng ưu tiên hiệu suất và chúng tôi sẽ không dừng lại ở đây. Hãy tiếp tục và chuẩn bị trước từ điển bằng số không. Sau đó, chúng tôi sẽ không phải kiểm tra mọi lúc nếu mặt hàng đó đã ở đó

ngả mũ trước @sqram

>>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
0

Tốt đấy. Nhanh gấp ba lần so với 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
0, nhưng vẫn đủ đơn giản. Cá nhân, đây là mục yêu thích của tôi trong trường hợp bạn không muốn thêm ký tự mới sau này. Và ngay cả khi bạn làm, bạn vẫn có thể làm được. Nó chỉ kém tiện lợi hơn so với các phiên bản khác

>>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
1

Tính thực tế đánh bại sự thuần khiết [trừ khi nó không thực sự thực tế]

Bây giờ một loại quầy hơi khác. @IdanK đã nghĩ ra một điều thú vị. Thay vì sử dụng một bảng băm [a. k. a. từ điển một. k. a. 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
1], chúng ta có thể tránh rủi ro xung đột hàm băm và do đó chi phí giải quyết của chúng. Chúng ta cũng có thể tránh được chi phí băm khóa và không gian bảng trống bổ sung. Chúng ta có thể sử dụng một 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except:
..     d[c] = 1
.. ''', globals=locals[]]
3.3506563019982423
8. Các giá trị ASCII của các ký tự sẽ là các chỉ số và số lượng của chúng sẽ là các giá trị. Như @IdanK đã chỉ ra, danh sách này cho phép chúng tôi truy cập thời gian liên tục vào số lượng ký tự. Tất cả những gì chúng ta phải làm là chuyển đổi từng ký tự từ 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except:
..     d[c] = 1
.. ''', globals=locals[]]
3.3506563019982423
9 thành 
import time
while True:
  try:
    time.sleep[1]
  except:
    print["You're trapped in your own trap!"]
0 bằng hàm tích hợp sẵn 
import time
while True:
  try:
    time.sleep[1]
  except:
    print["You're trapped in your own trap!"]
1. Điều đó sẽ cung cấp cho chúng tôi một chỉ mục trong danh sách, sau đó chúng tôi sẽ sử dụng chỉ mục này để tăng số lượng ký tự. Vì vậy, những gì chúng tôi làm là đây. chúng tôi khởi tạo danh sách bằng số 0, thực hiện công việc và sau đó chuyển đổi danh sách thành 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
1. 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
1 này sẽ chỉ chứa những ký tự có số lượng khác 0, để làm cho nó phù hợp với các phiên bản khác

Lưu ý thêm, kỹ thuật này được sử dụng trong thuật toán sắp xếp theo thời gian tuyến tính được gọi là sắp xếp đếm hoặc sắp xếp đếm. Nó rất hiệu quả, nhưng phạm vi giá trị được sắp xếp bị hạn chế, vì mỗi giá trị phải có bộ đếm riêng. Để sắp xếp một chuỗi các số nguyên 32 bit, 4. 3 tỷ quầy sẽ là cần thiết

>>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
2

ôi. Không mát mẻ. Hãy thử xem chúng ta bỏ qua việc xây dựng từ điển sẽ mất bao lâu

>>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
3

Vẫn tệ. Nhưng chờ đã, 

import time
while True:
  try:
    time.sleep[1]
  except:
    print["You're trapped in your own trap!"]
4 là gì? . Nhưng nó sẽ hoạt động tốt hơn?

>>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
4

đáng kể. Bây giờ hãy đặt từ điển trở lại

>>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
5

Chậm hơn gần sáu lần. Tại sao phải mất quá lâu? . Nhưng chúng ta đã biết số nào bằng 0 và số nào không

>>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
6

Nó có thể sẽ không tốt hơn thế nhiều, ít nhất là không cho một đầu vào nhỏ như vậy. Ngoài ra, nó chỉ có thể sử dụng được cho các ký tự EASCII 8 bit. О блять

>>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
7

Chuẩn rồi. Ngay cả khi bạn phải kiểm tra mọi lúc xem 

import time
while True:
  try:
    time.sleep[1]
  except:
    print["You're trapped in your own trap!"]
7 có ở trong 
import time
while True:
  try:
    time.sleep[1]
  except:
    print["You're trapped in your own trap!"]
8 hay không, đối với thông tin đầu vào này, đó là cách nhanh nhất. Không có dân số trước của 
import time
while True:
  try:
    time.sleep[1]
  except:
    print["You're trapped in your own trap!"]
8 sẽ làm cho nó nhanh hơn [một lần nữa, đối với đầu vào này]. Nó dài dòng hơn nhiều so với 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
0 hoặc 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except:
..     d[c] = 1
.. ''', globals=locals[]]
3.3506563019982423
4, nhưng cũng hiệu quả hơn

Bài tập nhỏ này dạy cho chúng ta một bài học. khi tối ưu hóa, luôn đo lường hiệu suất, lý tưởng nhất là với thông tin đầu vào dự kiến ​​của bạn. Tối ưu hóa cho trường hợp phổ biến. Đừng cho rằng thứ gì đó thực sự hiệu quả hơn chỉ vì độ phức tạp tiệm cận của nó thấp hơn. Và cuối cùng nhưng không kém phần quan trọng, hãy ghi nhớ khả năng đọc. Cố gắng tìm sự thỏa hiệp giữa "thân thiện với máy tính" và "thân thiện với con người"

CẬP NHẬT

Tôi đã được thông báo bởi @MartijnPieters về chức năng 

import sys
try:
  print["Goodbye. I'm going to die soon."]
  sys.exit[]
except:
  print['BACK FROM THE DEAD!!!']
2 có sẵn trong Python 3

>>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
8

Chức năng này được triển khai trong C, vì vậy nó sẽ nhanh hơn, nhưng hiệu suất bổ sung này có giá. Giá không tương thích với Python 2 và thậm chí có thể là các phiên bản trong tương lai, vì chúng tôi đang sử dụng một chức năng riêng tư

Từ

[. ] tên có tiền tố là dấu gạch dưới [e. g. 

import sys
try:
  print["Goodbye. I'm going to die soon."]
  sys.exit[]
except:
  print['BACK FROM THE DEAD!!!']
3] nên được coi là một phần không công khai của API [cho dù đó là một hàm, một phương thức hay một thành viên dữ liệu]. Nó nên được coi là một chi tiết thực hiện và có thể thay đổi mà không cần thông báo

Điều đó nói rằng, nếu bạn vẫn muốn tiết kiệm 620 nano giây đó cho mỗi lần lặp lại

>>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
9

Tôi nghĩ rằng có thể nên chạy lại các thử nghiệm trên một số đầu vào lớn hơn, vì chuỗi 16 ký tự là một đầu vào nhỏ đến mức tất cả các giải pháp khả thi đều khá nhanh [1.000 lần lặp lại trong vòng chưa đầy 30 mili giây]

Tôi quyết định sử dụng các tác phẩm hoàn chỉnh của Shakespeare làm kho dữ liệu thử nghiệm, điều này hóa ra lại là một thách thức khá lớn [vì nó có kích thước hơn 5MiB 😅]. Tôi chỉ sử dụng 100.000 ký tự đầu tiên của nó và tôi phải giới hạn số lần lặp lại từ 1.000.000 đến 1.000

>>> timeit['{c: s.count[c] for c in s}', globals=locals[]]
4.551155784000002
0

>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
9 thực sự rất chậm với một thông tin đầu vào nhỏ, nhưng tình thế đã thay đổi

>>> timeit['{c: s.count[c] for c in s}', globals=locals[]]
4.551155784000002
1

Việc hiểu từ điển thời gian Naïve Θ[n2] đơn giản là không hoạt động

>>> timeit['{c: s.count[c] for c in s}', globals=locals[]]
4.551155784000002
2

Khả năng hiểu từ điển thời gian Θ[n] thông minh hoạt động tốt

>>> timeit['{c: s.count[c] for c in s}', globals=locals[]]
4.551155784000002
3

Ngoại lệ là vụng về và chậm

>>> timeit['{c: s.count[c] for c in s}', globals=locals[]]
4.551155784000002
4

Bỏ qua kiểm tra loại ngoại lệ không tiết kiệm thời gian [vì ngoại lệ chỉ được ném một vài lần]

>>> timeit['{c: s.count[c] for c in s}', globals=locals[]]
4.551155784000002
5

import sys
try:
  print["Goodbye. I'm going to die soon."]
  sys.exit[]
except:
  print['BACK FROM THE DEAD!!!']
5 trông đẹp nhưng chạy chậm

>>> timeit['{c: s.count[c] for c in s}', globals=locals[]]
4.551155784000002
6

import sys
try:
  print["Goodbye. I'm going to die soon."]
  sys.exit[]
except:
  print['BACK FROM THE DEAD!!!']
6 cũng không nhanh lắm

>>> timeit['{c: s.count[c] for c in s}', globals=locals[]]
4.551155784000002
7

import sys
try:
  print["Goodbye. I'm going to die soon."]
  sys.exit[]
except:
  print['BACK FROM THE DEAD!!!']
7 yêu cầu đọc chuỗi [rất dài] hai lần

>>> timeit['{c: s.count[c] for c in s}', globals=locals[]]
4.551155784000002
8

Sử dụng 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except:
..     d[c] = 1
.. ''', globals=locals[]]
3.3506563019982423
8 thay vì 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
1 không đẹp và cũng không nhanh

>>> timeit['{c: s.count[c] for c in s}', globals=locals[]]
4.551155784000002
9

Bỏ qua chuyển đổi cuối cùng thành 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
1 không giúp được gì

>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
0

Việc bạn xây dựng 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except:
..     d[c] = 1
.. ''', globals=locals[]]
3.3506563019982423
8 như thế nào không quan trọng, vì đó không phải là nút cổ chai

>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
1
>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
2

Nếu bạn chuyển đổi 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except:
..     d[c] = 1
.. ''', globals=locals[]]
3.3506563019982423
8 thành 
>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
1 theo cách "thông minh", thì thậm chí còn chậm hơn [vì bạn lặp lại chuỗi hai lần]

>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
3

Biến thể 

>>> timeit['''
.. d = {}
.. for c in s:
..   d[c] = d.get[c, 0] + 1
.. ''', globals=locals[]]
3.2133633289995487
4 có thể nhanh đối với chuỗi nhỏ, nhưng không quá nhiều đối với chuỗi lớn

>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
4

import sys
try:
  print["Goodbye. I'm going to die soon."]
  sys.exit[]
except:
  print['BACK FROM THE DEAD!!!']
2 nhanh bằng khoảng 
>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
9 [sử dụng nội bộ 
>>> timeit['''
.. d = {}
.. for c in s:
..   d[c] = d.get[c, 0] + 1
.. ''', globals=locals[]]
3.2133633289995487
7]

>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
5

Phán quyết cuối cùng. Sử dụng 
>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
9 trừ khi bạn không thể hoặc không muốn. ]

ruột thừa. NumPy

Gói 

>>> timeit['''
.. d = {}
.. for c in s:
..   d[c] = d.get[c, 0] + 1
.. ''', globals=locals[]]
3.2133633289995487
9 cung cấp một phương thức 
>>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
0 hoàn thành [gần như] chính xác những gì chúng ta muốn

Cách thức hoạt động của phương pháp này rất khác so với tất cả các phương pháp trên

  • Đầu tiên, nó sắp xếp một bản sao của đầu vào bằng cách sử dụng Quicksort, đây là thao tác theo thời gian O[n2] trong trường hợp xấu nhất, mặc dù trung bình là O[n log n] và O[n] trong trường hợp tốt nhất

  • Sau đó, nó tạo ra một mảng "mặt nạ" chứa 

    >>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
    1 tại các chỉ số bắt đầu chạy các giá trị giống nhau, viz. tại các chỉ số mà giá trị khác với giá trị trước đó. Các giá trị lặp lại tạo ra 
    >>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
    2 trong mặt nạ. Thí dụ. 
    >>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
    3 sản xuất mặt nạ 
    >>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
    4

  • Sau đó, mặt nạ này được sử dụng để trích xuất các giá trị duy nhất từ ​​đầu vào đã sắp xếp - 

    >>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
    5 trong mã bên dưới. Trong ví dụ của chúng ta, chúng sẽ là 
    >>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
    6

  • Vị trí của các giá trị 

    >>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
    1 trong mặt nạ được đưa vào một mảng và độ dài của đầu vào được thêm vào cuối mảng này. Đối với ví dụ trên, mảng này sẽ là 
    >>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
    8

  • Đối với mảng này, sự khác biệt giữa các phần tử của nó được tính toán, ví dụ:. 

    >>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
    9. Đây là số lượng tương ứng của các phần tử trong mảng đã sắp xếp ‒ 
    >>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
    00 trong mã bên dưới

  • Cuối cùng, chúng tôi tạo một từ điển bằng cách nén 

    >>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
    5 và 
    >>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
    00. 
    >>> timeit['Counter[s]', globals=locals[]]
8.208566107001388
    03

>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
6

Đối với đầu vào thử nghiệm [100.000 ký tự đầu tiên của toàn bộ tác phẩm của Shakespeare], phương pháp này hoạt động tốt hơn bất kỳ phương pháp nào khác được thử nghiệm tại đây. Nhưng lưu ý rằng trên một đầu vào khác, phương pháp này có thể mang lại hiệu suất kém hơn so với các phương pháp khác. Sự sắp xếp trước của đầu vào và số lần lặp lại trên mỗi phần tử là những yếu tố quan trọng ảnh hưởng đến hiệu suất

>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
7


Nếu bạn đang nghĩ đến việc sử dụng phương pháp này vì nó nhanh hơn gấp đôi so với 

>>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
9, hãy xem xét phương pháp này

  • >>> timeit['{c: s.count[c] for c in set[s]}', globals=locals[]]
3.1484066140001232
    9 có độ phức tạp thời gian tuyến tính. 
    >>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
    0 tốt nhất là tuyến tính, tệ nhất là bậc hai

  • Việc tăng tốc không thực sự đáng kể ‒ bạn tiết kiệm được ~3. 5 mili giây mỗi lần lặp trên đầu vào có độ dài 100.000

  • Sử dụng 

    >>> timeit['''
.. dd = defaultdict[int]
.. for c in s:
..   dd[c] += 1
.. ''', globals=locals[]]
3.3430528169992613
    0 rõ ràng yêu cầu 
    >>> timeit['''
.. d = {}
.. for c in s:
..   d[c] = d.get[c, 0] + 1
.. ''', globals=locals[]]
3.2133633289995487
    9

Điều đó được xem xét, có vẻ hợp lý khi sử dụng 

>>> timeit['''
.. d = {}
.. for c in s:
..   try:
..     d[c] += 1
..   except KeyError:
..     d[c] = 1
.. ''', globals=locals[]]
3.7060273620008957
0 trừ khi bạn cần thực sự nhanh. Và trong trường hợp đó, tốt hơn hết bạn nên biết mình đang làm gì, nếu không, cuối cùng bạn sẽ chậm hơn với 
>>> timeit['''
.. d = {}
.. for c in s:
..   d[c] = d.get[c, 0] + 1
.. ''', globals=locals[]]
3.2133633289995487
9 so với khi không có nó

Phụ lục 2. Một âm mưu hơi hữu ích

Tôi đã chạy 13 phương pháp khác nhau ở trên trên các tiền tố của toàn bộ tác phẩm của Shakespeare và tạo một cốt truyện tương tác. Lưu ý rằng trong biểu đồ, cả tiền tố và thời lượng đều được hiển thị theo thang logarit [tiền tố được sử dụng có độ dài tăng theo cấp số nhân]. Nhấp vào các mục trong chú giải để hiển thị/ẩn chúng trong cốt truyện

Bài Viết Liên Quan

Hết hạnSau giây MongoDB
Làm cách nào để tạo vòng lặp for trong JavaScript?
Eurovision 2023 cuối cùng là ngày nào?
Cách nâng cấp PHP Debian
Danh sách định dạng chuỗi python độ dài không xác định
Làm cách nào để thêm trình phát mp3 vào html của tôi?
Base64 sang python thập phân
Public_html vị trí wordpress
Chúng ta có thể lưu trữ đối tượng trong JavaScript đối tượng không?
Tổng của mỗi số thứ n trong python
Trung tâm div bootstrap
Làm cách nào để tạo dữ liệu ngẫu nhiên trong excel?
Cột ngày tháng trên google sheet
Tính tổng của mảng trong PHP bằng vòng lặp for
Loại nội dung PHP
Làm cách nào để kích hoạt xác thực JWT?
Làm thế nào để bạn hiển thị phụ âm trong python?
Cheerio tải tệp HTML
Dấu thời gian tệp python
33wh bằng bao nhiêu

Toplist mới

#1
Top 7 sự tích hồ gươm - ngữ văn lớp 6 2023
6 tháng trước
#2
Top 7 gdcd 6 bài 1 kết nối tri thức 2023
6 tháng trước
#3
Top 7 ý nghĩa của xây dựng gia đình văn hóa 2023
6 tháng trước
#4
Top 6 mẫu hợp đồng mượn đất làm nhà xưởng 2023
6 tháng trước
#5
Top 3 tổng tài biến thái tôi yêu anh tập 27 2023
6 tháng trước
#6
Top 6 kết thực phim mỹ nhân vô lệ 2023
6 tháng trước
#7
Top 9 trong những câu thơ sau câu nào sử dụng thành ngữ 2023
6 tháng trước
#8
Top 8 đề tài và chủ de của tác phẩm tắt đèn 2023
6 tháng trước
#9
Top 5 tiểu sử của thầy thích pháp hòa 2023
6 tháng trước

Bài mới nhất

Chủng chuẩn e.coli atcc 25922 là gì năm 2024
Phục hồi nút erase trong cs6 bị lỗi năm 2024
Chương trình giải toán giải toán đại số năm 2024
Dì ruột bán cháu ở thường xuân thanh hóa năm 2024
Kiến bu quần lót là hiện tượng gì năm 2024

Chủ Đề

programming Hỏi Đáp Toplist Là gì Bài Tập Địa Điểm Hay Mẹo Hay Học Tốt Nghĩa của từ Công Nghệ Khỏe Đẹp bao nhiêu Top List Tiếng anh Bao nhiêu Sản phẩm tốt Xây Đựng Ngôn ngữ javascript Ở đâu Đại học Hướng dẫn Bài tập Tại sao Dịch So Sánh Máy tính Món Ngon mẹo hay Bao lâu Thế nào So sánh Khoa Học Vì sao Lớp 9 Lớp 10