acmpesuecc / acmpesuecc/traffic_simulation

Data Structure Alternatives - Commenting on efficiency

Abierto
#8 46 comentarios 0 reacciones 1 asignado Reclamado por @sameermanvi Ver en GitHub
BOUNTY:75 hacknight-2025 hacktoberfest
Lenguaje dominante
Python
Estrellas
1
Forks
13
Métricas de merge de PR
Sin PR fusionados en 30 d

Descripción

# Bounty Points: 75

## Branch Instructions
push changes to a new *'ds'* branch

***

**Explanation:**

Current clock list management is **inefficient**
Removes items while iterating: `for i in clock: if i[2]==t: clock.remove(i)`
$O(n^2)$ complexity due to `list.remove()` in loop
No priority queue for event scheduling

Current problematic code:
```python
for i in clock:
if i[2] == t:
clock.remove(i) # $O(n)$ operation in $O(n)$ loop
```
### Possible fix/approach:

* Replace list with **`heapq`**-based **priority queue**
* Use event-based scheduling with `(time, event\_data)`
* Alternative: **dictionary** with time as key
* Benchmark before/after improvements
* Document complexity improvements

---

### Maintainer notes:

* Current approach causes **performance issues** with large graphs
* Focus on **clock/event management data structure**
* Should maintain same simulation logic

---

### Resources:

* Python `heapq` documentation
* Event-driven simulation patterns

---

Guía de contribución

Abrir la guía de contribución

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.