Algorithmes¶
Mesurer le temps¶
[1]:
def fonction1():
raise RuntimeError("stop")
def fonction2():
return fonction1()
def fonction3():
return fonction2()
try:
fonction3()
except Exception as e:
print([type(e), e])
[<class 'RuntimeError'>, RuntimeError('stop')]
[2]:
def recherche_list(ensemble: list, element) -> bool:
return element in ensemble
def recherche_set(ensemble: set, element) -> bool:
return element in ensemble
def recherche_dict(ensemble: dict, element) -> bool:
return element in ensemble
N = 10000
list_entier = list(range(N))
set_entier = set(range(N))
dict_entier = {k: 0 for k in range(N)}
T = 100
import time
begin = time.time()
for i in range(T):
recherche_list(list_entier, 9000)
duree = time.time() - begin
print("list", duree)
list 0.00920867919921875
[3]:
T = 10000
el = 9999
begin = time.time()
for i in range(T):
recherche_list(list_entier, el)
duree = time.time() - begin
print("list", duree)
begin = time.time()
for i in range(T):
recherche_set(set_entier, el)
duree = time.time() - begin
print("set", duree)
begin = time.time()
for i in range(T):
recherche_dict(dict_entier, el)
duree = time.time() - begin
print("dict", duree)
list 0.6168732643127441
set 0.0010602474212646484
dict 0.0015003681182861328
[4]:
import hashlib
# Texte à hacher
texte = "Bonjour le mondesdナルト".encode("utf-8")
print(texte)
# Création du hash SHA-256
hash_obj = hashlib.sha256(texte)
hash_hex = hash_obj.hexdigest()[:10]
print(hash_hex)
b'Bonjour le mondesd\xe3\x83\x8a\xe3\x83\xab\xe3\x83\x88'
9b158061cd
Profiling¶
[5]:
def f():
for i in range(T):
recherche_list(list_entier, el)
recherche_set(set_entier, el)
recherche_dict(dict_entier, el)
[6]:
from pyinstrument import Profiler
profiler = Profiler()
profiler.start()
# Code à profiler
f()
profiler.stop()
print(profiler.output_text())
_ ._ __/__ _ _ _ _ _/_ Recorded: 22:16:49 Samples: 643
/_//_/// /_\ / //_// / //_'/ // Duration: 0.664 CPU time: 0.669
/ _/ v5.1.1
Profile at /tmp/ipykernel_231901/1337574655.py:4
0.663 ZMQInteractiveShell.run_ast_nodes IPython/core/interactiveshell.py:3418
`- 0.662 <module> /tmp/ipykernel_231901/1337574655.py:1
`- 0.662 f /tmp/ipykernel_231901/2115577803.py:1
|- 0.648 recherche_list /tmp/ipykernel_231901/3550779215.py:1
`- 0.012 [self] /tmp/ipykernel_231901/2115577803.py
[7]:
%prun f()
30757 function calls (30742 primitive calls) in 0.667 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
10000 0.638 0.000 0.638 0.000 3550779215.py:1(recherche_list)
1 0.007 0.007 0.459 0.459 2115577803.py:1(f)
6/4 0.007 0.001 0.007 0.002 events.py:86(_run)
2/1 0.005 0.003 0.459 0.459 <string>:1(<module>)
3/1 0.003 0.001 0.000 0.000 selectors.py:451(select)
10000 0.002 0.000 0.002 0.000 3550779215.py:4(recherche_set)
10000 0.002 0.000 0.002 0.000 3550779215.py:7(recherche_dict)
14 0.001 0.000 0.001 0.000 socket.py:626(send)
1 0.000 0.000 0.020 0.020 history.py:833(_writeout_input_cache)
3/1 0.000 0.000 0.000 0.000 {method 'poll' of 'select.epoll' objects}
2 0.000 0.000 0.006 0.003 socket.py:703(send_multipart)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
1 0.000 0.000 0.027 0.027 history.py:55(only_when_enabled)
2 0.000 0.000 0.000 0.000 {method 'recv' of '_socket.socket' objects}
2 0.000 0.000 0.000 0.000 {method '__exit__' of 'sqlite3.Connection' objects}
2 0.000 0.000 0.000 0.000 socket.py:774(recv_multipart)
4 0.000 0.000 0.171 0.043 base_events.py:1922(_run_once)
5 0.000 0.000 0.000 0.000 attrsettr.py:66(_get_attr_opt)
72 0.000 0.000 0.000 0.000 enum.py:1538(_get_value)
2/1 0.000 0.000 0.650 0.650 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {method 'execute' of 'sqlite3.Connection' objects}
152/148 0.000 0.000 0.000 0.000 {built-in method builtins.isinstance}
16 0.000 0.000 0.000 0.000 enum.py:1545(__or__)
1 0.000 0.000 0.000 0.000 poll.py:80(poll)
5 0.000 0.000 0.000 0.000 attrsettr.py:43(__getattr__)
2/1 0.000 0.000 0.027 0.027 decorator.py:229(fun)
31 0.000 0.000 0.000 0.000 enum.py:720(__call__)
1 0.000 0.000 0.000 0.000 {method 'send' of '_socket.socket' objects}
1 0.000 0.000 0.000 0.000 inspect.py:3133(_bind)
8 0.000 0.000 0.000 0.000 enum.py:1556(__and__)
6/4 0.000 0.000 0.001 0.000 {method 'run' of '_contextvars.Context' objects}
1 0.000 0.000 0.000 0.000 kernelbase.py:302(poll_control_queue)
31 0.000 0.000 0.000 0.000 enum.py:1123(__new__)
6 0.000 0.000 0.000 0.000 typing.py:392(inner)
2 0.000 0.000 0.006 0.003 iostream.py:278(_really_send)
1 0.000 0.000 0.020 0.020 history.py:845(writeout_cache)
2 0.000 0.000 0.007 0.003 zmqstream.py:583(_handle_events)
1 0.000 0.000 0.000 0.000 selector_events.py:129(_read_from_self)
1 0.000 0.000 0.000 0.000 traitlets.py:1527(_notify_observers)
8 0.000 0.000 0.000 0.000 traitlets.py:676(__get__)
3 0.000 0.000 0.000 0.000 zmqstream.py:686(_update_handler)
3 0.000 0.000 0.000 0.000 ioloop.py:742(_run_callback)
2 0.000 0.000 0.000 0.000 typing.py:1492(__subclasscheck__)
1 0.000 0.000 0.000 0.000 decorator.py:199(fix)
3 0.000 0.000 0.000 0.000 zmqstream.py:663(_rebuild_io_state)
2 0.000 0.000 0.006 0.003 iostream.py:157(_handle_event)
2 0.000 0.000 0.006 0.003 zmqstream.py:556(_run_callback)
1 0.000 0.000 0.000 0.000 kernelbase.py:324(_flush)
2 0.000 0.000 0.000 0.000 traitlets.py:3631(set)
4 0.000 0.000 0.000 0.000 queue.py:97(empty)
7 0.000 0.000 0.000 0.000 base_events.py:738(time)
2 0.000 0.000 0.006 0.003 zmqstream.py:624(_handle_recv)
1 0.000 0.000 0.000 0.000 queues.py:225(get)
8 0.000 0.000 0.000 0.000 traitlets.py:629(get)
3 0.000 0.000 0.000 0.000 base_events.py:818(_call_soon)
25 0.000 0.000 0.000 0.000 {built-in method builtins.len}
1 0.000 0.000 0.000 0.000 zmqstream.py:427(flush)
4 0.000 0.000 0.000 0.000 typing.py:1285(__hash__)
2 0.000 0.000 0.000 0.000 traitlets.py:708(__set__)
1 0.000 0.000 0.000 0.000 asyncio.py:225(add_callback)
5 0.000 0.000 0.000 0.000 selector_events.py:750(_process_events)
2 0.000 0.000 0.006 0.003 iostream.py:276(<lambda>)
1 0.000 0.000 0.000 0.000 _base.py:537(set_result)
1 0.000 0.000 0.000 0.000 iostream.py:718(_rotate_buffers)
1 0.000 0.000 0.000 0.000 iostream.py:616(_flush)
2 0.000 0.000 0.000 0.000 traitlets.py:689(set)
2 0.000 0.000 0.000 0.000 traitlets.py:718(_validate)
5 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:1390(_handle_fromlist)
1 0.000 0.000 0.000 0.000 threading.py:311(_acquire_restore)
1 0.000 0.000 0.000 0.000 inspect.py:2949(apply_defaults)
2 0.000 0.000 0.000 0.000 typing.py:1221(__instancecheck__)
5 0.000 0.000 0.000 0.000 {built-in method builtins.getattr}
1 0.000 0.000 0.000 0.000 inspect.py:3272(bind)
3 0.000 0.000 0.000 0.000 threading.py:299(__enter__)
2 0.000 0.000 0.000 0.000 base_events.py:1907(_add_callback)
10 0.000 0.000 0.000 0.000 {built-in method builtins.hasattr}
2 0.000 0.000 0.000 0.000 traitlets.py:3474(validate)
1 0.000 0.000 0.000 0.000 iostream.py:710(_flush_buffers)
1 0.000 0.000 0.000 0.000 queues.py:209(put_nowait)
2 0.000 0.000 0.000 0.000 traitlets.py:3624(validate_elements)
7 0.000 0.000 0.000 0.000 {built-in method time.monotonic}
1 0.000 0.000 0.000 0.000 queues.py:186(put)
3 0.000 0.000 0.000 0.000 events.py:36(__init__)
1 0.000 0.000 0.000 0.000 zmqstream.py:468(update_flag)
2 0.000 0.000 0.000 0.000 traitlets.py:727(_cross_validate)
7 0.000 0.000 0.000 0.000 {built-in method builtins.max}
3 0.000 0.000 0.000 0.000 threading.py:302(__exit__)
1 0.000 0.000 0.000 0.000 traitlets.py:1512(_notify_trait)
10 0.000 0.000 0.000 0.000 {method 'popleft' of 'collections.deque' objects}
1 0.000 0.000 0.000 0.000 inspect.py:2896(args)
1 0.000 0.000 0.000 0.000 inspect.py:2919(kwargs)
2 0.000 0.000 0.000 0.000 traitlets.py:2304(validate)
2 0.000 0.000 0.000 0.000 base_events.py:789(call_soon)
8 0.000 0.000 0.000 0.000 {method '__exit__' of '_thread.lock' objects}
1 0.000 0.000 0.000 0.000 traitlets.py:1523(notify_change)
9 0.000 0.000 0.000 0.000 {method 'append' of 'collections.deque' objects}
2 0.000 0.000 0.000 0.000 iostream.py:213(_is_master_process)
1 0.000 0.000 0.000 0.000 queues.py:256(get_nowait)
1 0.000 0.000 0.006 0.006 asyncio.py:200(_handle_events)
1 0.000 0.000 0.000 0.000 futures.py:396(_call_set_state)
1 0.000 0.000 0.000 0.000 threading.py:424(notify_all)
2 0.000 0.000 0.000 0.000 queues.py:322(_consume_expired)
1 0.000 0.000 0.000 0.000 threading.py:627(clear)
28 0.000 0.000 0.000 0.000 typing.py:2187(cast)
2 0.000 0.000 0.000 0.000 {built-in method builtins.issubclass}
4 0.000 0.000 0.000 0.000 zmqstream.py:542(sending)
5 0.000 0.000 0.000 0.000 {method 'upper' of 'str' objects}
2 0.000 0.000 0.000 0.000 <frozen abc>:121(__subclasscheck__)
6 0.000 0.000 0.000 0.000 {built-in method builtins.next}
2 0.000 0.000 0.000 0.000 {built-in method _abc._abc_subclasscheck}
1 0.000 0.000 0.000 0.000 base_events.py:842(call_soon_threadsafe)
6 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
2 0.000 0.000 0.000 0.000 {method 'set_result' of '_asyncio.Future' objects}
2 0.000 0.000 0.000 0.000 {built-in method builtins.min}
3 0.000 0.000 0.000 0.000 {method 'acquire' of '_thread.lock' objects}
2 0.000 0.000 0.000 0.000 iostream.py:216(_check_mp_mode)
1 0.000 0.000 0.000 0.000 history.py:839(_writeout_output_cache)
1 0.000 0.000 0.000 0.000 selector_events.py:141(_write_to_self)
2 0.000 0.000 0.000 0.000 {built-in method math.ceil}
1 0.000 0.000 0.000 0.000 concurrent.py:182(future_set_result_unless_cancelled)
1 0.000 0.000 0.000 0.000 _base.py:337(_invoke_callbacks)
3 0.000 0.000 0.000 0.000 {method 'items' of 'mappingproxy' objects}
1 0.000 0.000 0.000 0.000 queues.py:317(__put_internal)
2 0.000 0.000 0.000 0.000 selectors.py:275(_key_from_fd)
4 0.000 0.000 0.000 0.000 queue.py:209(_qsize)
1 0.000 0.000 0.000 0.000 threading.py:308(_release_save)
2 0.000 0.000 0.000 0.000 {built-in method _contextvars.copy_context}
1 0.000 0.000 0.000 0.000 {built-in method _asyncio.get_running_loop}
1 0.000 0.000 0.000 0.000 threading.py:394(notify)
2 0.000 0.000 0.000 0.000 {built-in method posix.getpid}
4 0.000 0.000 0.000 0.000 {method 'get' of 'dict' objects}
1 0.000 0.000 0.000 0.000 {built-in method _heapq.heappop}
1 0.000 0.000 0.000 0.000 {method 'values' of 'mappingproxy' objects}
4 0.000 0.000 0.000 0.000 {built-in method builtins.hash}
1 0.000 0.000 0.000 0.000 {method '__enter__' of '_thread.RLock' objects}
10 0.000 0.000 0.000 0.000 inspect.py:2808(kind)
1 0.000 0.000 0.000 0.000 {built-in method _thread.allocate_lock}
1 0.000 0.000 0.000 0.000 unix_events.py:81(_process_self_data)
2 0.000 0.000 0.000 0.000 traitlets.py:3486(validate_elements)
2 0.000 0.000 0.000 0.000 {method '__enter__' of '_thread.lock' objects}
5 0.000 0.000 0.000 0.000 zmqstream.py:538(receiving)
1 0.000 0.000 0.000 0.000 queues.py:173(qsize)
1 0.000 0.000 0.000 0.000 poll.py:31(register)
2 0.000 0.000 0.000 0.000 {built-in method builtins.iter}
2 0.000 0.000 0.000 0.000 {method '__exit__' of '_thread.RLock' objects}
1 0.000 0.000 0.000 0.000 zmqstream.py:694(<lambda>)
3 0.000 0.000 0.000 0.000 base_events.py:543(_check_closed)
5 0.000 0.000 0.000 0.000 base_events.py:2017(get_debug)
2 0.000 0.000 0.000 0.000 iostream.py:255(closed)
4 0.000 0.000 0.000 0.000 inspect.py:2796(name)
1 0.000 0.000 0.000 0.000 {method 'items' of 'dict' objects}
2 0.000 0.000 0.000 0.000 {method 'cancelled' of '_asyncio.Future' objects}
1 0.000 0.000 0.000 0.000 queues.py:309(_get)
1 0.000 0.000 0.000 0.000 zmqstream.py:659(_check_closed)
1 0.000 0.000 0.000 0.000 queues.py:312(_put)
4 0.000 0.000 0.000 0.000 inspect.py:3089(parameters)
2 0.000 0.000 0.000 0.000 {method 'extend' of 'list' objects}
1 0.000 0.000 0.000 0.000 threading.py:314(_is_owned)
1 0.000 0.000 0.000 0.000 queues.py:177(empty)
1 0.000 0.000 0.000 0.000 {method '_is_owned' of '_thread.RLock' objects}
1 0.000 0.000 0.000 0.000 {method 'done' of '_asyncio.Future' objects}
1 0.000 0.000 0.000 0.000 base_events.py:724(is_closed)
1 0.000 0.000 0.000 0.000 queues.py:59(_set_timeout)
1 0.000 0.000 0.000 0.000 {method 'release' of '_thread.lock' objects}
1 0.000 0.000 0.000 0.000 locks.py:224(clear)
1 0.000 0.000 0.000 0.000 inspect.py:2888(__init__)
Optimisation d’un programme¶
[8]:
import numpy as np
import matplotlib.pyplot as plt
def distance(v1, v2): # v1= np.array([0, 1]), v2= ....
return ((v1 - v2) ** 2).sum() ** 0.5
# return ((v1[0] - v2[0]) ** 2 + (v1[1] - v2[1]) ** 2) ** 0.5
def plus_proche_non_visitee(villes, chemin):
depart = chemin[-1]
dmin, imin = None, None
for i in range(villes.shape[0]):
if i not in chemin:
d = distance(villes[depart], villes[i])
if dmin is None or d < dmin:
dmin, imin = d, i
return imin
def algo_proche_en_proche(villes):
chemin = [0]
while len(chemin) < villes.shape[0]:
# trouver la ville la plus proche non visitée de la dernière
# ville visitée et l'ajouter au chemin
inext = plus_proche_non_visitee(villes, chemin)
chemin.append(inext)
return chemin
def elimine_croisements(villes, chemin):
C = chemin
while True:
mieux = 0
for i in range(-1, villes.shape[0]):
for j in range(i + 2, villes.shape[0] - 1):
delta = (
-distance(villes[C[i]], villes[C[i + 1]])
- distance(villes[C[j]], villes[C[j + 1]])
+ distance(villes[C[i]], villes[C[j]])
+ distance(villes[C[i + 1]], villes[C[j + 1]])
)
if delta < 0:
mieux += 1
if i >= 0:
chemin[i + 1 : j + 1] = chemin[j:i:-1]
else:
chemin[i + 1 : j + 1] = chemin[j::-1]
if mieux == 0:
break
villes = np.random.rand(20, 2)
chemin = algo_proche_en_proche(villes)
elimine_croisements(villes, chemin)
villes[:5], chemin
[8]:
(array([[0.02609378, 0.47304915],
[0.11827469, 0.76657083],
[0.827706 , 0.26337121],
[0.56057621, 0.53610594],
[0.22134542, 0.73108227]]),
[7, 19, 0, 9, 18, 8, 17, 15, 5, 14, 2, 13, 11, 12, 6, 16, 10, 1, 4, 3])
[9]:
def problem(N, T):
for t in range(T):
print("t=", t, "N=", N)
villes = np.random.rand(N, 2)
chemin = algo_proche_en_proche(villes)
elimine_croisements(villes, chemin)
return chemin
print(problem(100, 1))
t= 0 N= 100
[75, 51, 15, 20, 73, 40, 82, 38, 59, 94, 36, 54, 88, 26, 97, 44, 81, 13, 96, 99, 28, 9, 14, 78, 46, 85, 83, 22, 93, 52, 2, 56, 42, 27, 49, 25, 62, 39, 5, 92, 34, 21, 66, 16, 30, 37, 70, 57, 76, 86, 63, 33, 19, 58, 43, 23, 65, 3, 45, 72, 77, 0, 60, 32, 89, 4, 61, 71, 84, 79, 18, 87, 67, 31, 24, 74, 50, 10, 91, 68, 98, 1, 64, 41, 48, 95, 80, 69, 29, 55, 12, 47, 6, 11, 35, 90, 17, 7, 53, 8]
import cProfile, pstats, io
from pstats import SortKey
pr = cProfile.Profile()
pr.enable()
problem(10, 5)
pr.disable()
s = io.StringIO()
sortby = SortKey.CUMULATIVE
ps = pstats.Stats(pr, stream=s).sort_stats(sortby)
ps.print_stats()
print(s.getvalue().replace("<ipython-input-", "<nb"))
Optimisation de la fonction distance¶
[10]:
def distance1(v1, v2): # v1= np.array([0, 1]), v2= ....
return ((v1 - v2) ** 2).sum() ** 0.5
def distance2(v1, v2):
s = (v1 - v2) ** 2
return (s[0] + s[1]) ** 0.5
def distance3(v1, v2):
d = v1 - v2
s = d * d
return np.sqrt(s[0] + s[1])
import numpy as np
v1 = np.array([0, 5], dtype=np.float32)
v2 = np.array([1, 5.5], dtype=np.float32)
N = 100000
import time
begin = time.time()
for i in range(N):
distance1(v1, v2)
print("duree", time.time() - begin)
begin = time.time()
for i in range(N):
distance2(v1, v2)
print("duree", time.time() - begin)
begin = time.time()
for i in range(N):
distance3(v1, v2)
print("duree", time.time() - begin)
duree 0.2855997085571289
duree 0.14869189262390137
duree 0.22153949737548828
[11]:
def distance(v1, v2):
d = v1 - v2
s = d * d
return np.sqrt(s[0] + s[1])
def delta(villes, C, i, j):
i1, i2, j1, j2 = C[i], C[i + 1], C[j], C[j + 1]
return (
-distance(villes[i1], villes[i2])
- distance(villes[j1], villes[j2])
+ distance(villes[i1], villes[j1])
+ distance(villes[i2], villes[j2])
)
def delta2(villes, C, i, j):
i1, i2, j1, j2 = C[i], C[i + 1], C[j], C[j + 1]
d = villes[(i1, j1, i1, i2), :] - villes[(i2, j2, j1, j2), :]
d2 = d * d
s = np.sqrt(d2[:, 0] + d2[:, 1])
return -s[0] - s[1] + s[2] + s[3]
villes = np.random.rand(20, 2)
C = list(range(villes.shape[0]))
delta(villes, C, 5, 8), delta2(villes, C, 5, 8)
[11]:
(np.float64(0.0054706211079842415), np.float64(0.0054706211079842415))
[12]:
begin = time.time()
for i in range(N):
delta(villes, C, 5, 8)
print("duree", time.time() - begin)
begin = time.time()
for i in range(N):
delta2(villes, C, 5, 8)
print("duree", time.time() - begin)
duree 1.044642686843872
duree 0.844332218170166
[13]:
import scipy
def elimine_croisements2(villes, chemin):
distances = scipy.spatial.distances.pdist(villes)
C = chemin
while True:
mieux = 0
for i in range(-1, villes.shape[0]):
for j in range(i + 2, villes.shape[0] - 1):
delta = (
-distances[C[i], C[i + 1]]
- distances[C[j], C[j + 1]]
+ distances[C[i], C[j]]
+ distances[C[i + 1], C[j + 1]]
)
if delta < 0:
mieux += 1
print("mieux", i, j, delta, chemin[i + 1 : j + 1], chemin[j:i:-1])
# c'est mieux... on retourne les villes du chemin
# entre i+1 et j inclus
if i >= 0:
chemin[i + 1 : j + 1] = chemin[j:i:-1]
else:
chemin[i + 1 : j + 1] = chemin[j::-1]
if mieux == 0:
break
[ ]:
Préfixes¶
[14]:
def casse_liste(liste):
premiere_lettre = set(mot[:1] for mot in liste)
res = {}
for p in premiere_lettre:
res[p] = [mot[1:] for mot in liste if mot[:1] == p]
return res
liste = ["AB", "ABC", "BA", "BCA", "B", "EE", "EF", "EG", ""]
casse_liste(liste)
[14]:
{'': [''], 'B': ['A', 'CA', ''], 'E': ['E', 'F', 'G'], 'A': ['B', 'BC']}
[15]:
def casse_liste_rec(liste):
if not liste or liste == [""]:
return {}
premiere_lettre = set(mot[:1] for mot in liste)
res = {}
for p in premiere_lettre:
res[p] = casse_liste_rec([mot[1:] for mot in liste if mot[:1] == p])
return res
liste = ["AB", "ABC", "BA", "BCA", "B", "EE", "EF", "EG", ""]
casse_liste_rec(liste)
[15]:
{'': {},
'B': {'C': {'A': {}}, '': {}, 'A': {}},
'E': {'E': {}, 'F': {}, 'G': {}},
'A': {'B': {'': {}, 'C': {}}}}
[16]:
import pprint
pprint.pprint(casse_liste_rec(liste))
{'': {},
'A': {'B': {'': {}, 'C': {}}},
'B': {'': {}, 'A': {}, 'C': {'A': {}}},
'E': {'E': {}, 'F': {}, 'G': {}}}
[17]:
def reconstruit_liste(trie, prefixe=""):
mots = []
for lettre, sous_trie in trie.items():
nouveau_prefixe = prefixe + lettre
if not sous_trie: # Si le sous-trie est vide, c'est la fin d'un mot
mots.append(nouveau_prefixe)
else:
mots.extend(reconstruit_liste(sous_trie, nouveau_prefixe))
return mots
liste = ["AB", "ABC", "BA", "BCA", "B", "EE", "EF", "EG", ""]
trie = casse_liste_rec(liste)
liste_reconstruite = reconstruit_liste(trie)
liste_reconstruite
[17]:
['', 'BCA', 'B', 'BA', 'EE', 'EF', 'EG', 'AB', 'ABC']
[18]:
def search_trie(trie, mot):
if not mot:
return True # Mot vide, considéré comme présent
if not trie:
return False # Trie vide, mot absent
premiere_lettre = mot[0]
if premiere_lettre not in trie:
return False
return search_trie(trie[premiere_lettre], mot[1:])
search_trie(trie, ""), search_trie(trie, "BC"), search_trie(trie, "Z")
[18]:
(True, True, False)
[19]:
def search_trie2(trie, mot):
current = trie
for lettre in mot:
if lettre not in current:
return False
current = current[lettre]
return True
search_trie2(trie, ""), search_trie2(trie, "BC"), search_trie2(trie, "Z")
[19]:
(True, True, False)
[20]:
def intersection_tries_naive(trie1, trie2):
liste = reconstruit_liste(trie1)
return [mot for mot in liste if search_trie2(trie2, mot)]
liste1 = ["AB", "ABC", "BA", "BCA", "B", "EE", "EF", "EG"]
trie1 = casse_liste_rec(liste1)
liste2 = ["AB", "BA", "BCA", "B", "EE", "EF", "EG", "EH"]
trie2 = casse_liste_rec(liste2)
intersection_tries_naive(trie1, trie2)
[20]:
['BCA', 'B', 'BA', 'EE', 'EF', 'EG', 'AB']
[21]:
def intersection_tries(trie1, trie2, prefixe=""):
mots = []
# Parcourir les clés communes aux deux tries
for lettre in set(trie1.keys()) & set(trie2.keys()):
nouveau_prefixe = prefixe + lettre
# Si les deux sous-tries sont vides, c'est un mot commun
if not trie1[lettre] and not trie2[lettre]:
mots.append(nouveau_prefixe)
else:
# Sinon, continuer récursivement
mots.extend(
intersection_tries(trie1[lettre], trie2[lettre], nouveau_prefixe)
)
return mots
intersection_tries(trie1, trie2)
[21]:
['BCA', 'B', 'BA', 'EE', 'EF', 'EG']
[ ]: