改进player.playlist的数据结构

[chen-chao]

player.playlist 里使用list来存放歌曲, 在查询/添加/删除歌曲的时候复杂度均为O(n). 如果想要支持衍生的一些想法中几万张专辑这样的大歌单, 应该会非常低效.

目前有两个想法:

1. linked list: 利用一个链表来存放歌曲, 然后用一个dict索引 song->linked list node, 从而维护歌单的有序结构.
2. list with empty slots: 同样利用list和dict存放歌曲, 删除歌曲的时候设为None保留空位, 然后当歌曲小于2/3 list长度的时候resize.

3种方案比较:

operation	raw list	linked list	list with empty slots
append	O(N)	O(1)	O(1)
search	O(N)	O(1)	O(1)
remove	O(N)	O(1)	Amortized O(1)
memory	song size	song size + dict size + references x N	song size + dict size
drawback	too slow	can't directly access by index	insertion after a song is O(N)

目前利用整数代替歌曲测试, 添加100000整数, 然后随机删除:

• raw list: append 95.6s, remove 70.2s ;
• linked list: append 0.35s, remove 0.26s;
• list with empty slots: append 0.05s, remove 0.12s.

可以看到第三种方案相当迅速(linked list需要在nodes 之间跳转), 但缺点在于插入歌曲时的效率依然较差.

另外, 我觉得在playlist里不必要维护 good songs和bad songs, 在 player播放有误的时候跳过就好了.

[cosven]

哇，太赞了！学习-ing
先讨论一下其中简单一点的问题

playlist 里不必要维护 good songs 和 bad songs, 在 player 播放有误的时候跳过就好了

目前的考虑主要是如果歌单里面全是 bad songs 的时候，player 会进入一个死循环的状态。
个人感觉要解决这个问题：总是需要一个方法来对歌曲进行标记，知道哪些是好的，哪些是坏的。

---

然后是关于 playlist 的性能优化问题，其实我之前还真没怎么考虑过性能方面的事情，感谢大佬带领了一个好的开始。下面是我的读后感：

目前自己想到的出现 添加一首歌曲 的情况：（感觉两种操作频率应该都不低）

• 用户指定播放某一首歌
  （在目前的设计中）会把这首歌曲放到当前播放歌曲的后面，相当于是一个 insert 操作
  这时候上面第二种方案是 O(1)，第一和第三方案都是 O(n)
• 用户添加某一首歌到播放列表
  这个操作是 append 操作
  这时候三种方案都是 O(1) （上面说的 list append 操作是 O(n) 是不是不太对？ref）

对于 search 操作我有一点疑问：什么情况会有 search 操作呢，我目前感觉只有 insert 的时候才会用到搜索？（虽然播放下一首，播放上一首这样的情况也会用到，但是这两种情况或许是可以通过添加 current_index 这样一个标记来解决）

另外我有个疑虑是第二种方案和第三种方案在实际情形中分别会多占用多少空间？

对于第二种方案，有另外一个疑惑：链表这种数据结构怎样实现随机播放模式呢？在随机播放模式下，它的时间复杂度又是多少呢？

---

对于测试结果，有点疑问：

raw list: append 95.6s, remove 70.2s ;

这个是说，当 list 长度为 100,000 时，append 一个数字会花费 95s 么？还是说 append 100000 个数字总共话费 95s 呢？

---

总的来说，个人有下面几个结论或者观点：

1. 纯 list 在 search/remove/insert 都太慢
2. linked list + dict 在顺序播放模式下时间复杂度上表现好，但不确定随机模式下表现如何？另外空间占用情况怎样也不太确定。
3. list with empty slots + dict 方案改进了 list search/remove 的性能，但是 insert 还是很慢。另外目前好像没有 search 的需求？
4. 所以是不是只有第二种方案可以适应 100000 首歌这样的场景（如果存在的话）

最后，感谢 lz 的方案，受益匪浅 ～
感觉可以哪天爬一点数据下来，真实的测试一下

---

给自己记录几个 TODO

• 调研 QMediaPlayer 中 playlist 的实现（或者其它 playlist）
• 爬数据，测试这些方案的内存占用情况
  • 顺便测试 __slots__ = () 是否可以节约内存

[chen-chao]

上面说的 list append 操作是 O(n) 是不是不太对？

目前的playlist的实现里每次添加歌曲的时候会查询是否已存在, 所以 raw list的append是O(N). 一般情况下我觉得总是需要一个dict来建立索引.

这个是说，当 list 长度为 100,000 时，append 一个数字会花费 95s 么...

是添加和删除的总时间. 单次O(N)操作对计算机来说其实不算什么. 但是 feeluown.containers.table_container.SongTableContainer.play_all 里有加载全部歌曲到歌单的操作. 而且我觉得把当前歌曲列表作为歌单也是很正常的行为. 这个时候耗时就很可观了. 而且可以肯定的是, 直接对 song model 操作肯定比整数慢.

linked list + dict 在顺序播放模式下时间复杂度上表现好，但不确定随机模式下表现如何？

随机模式目前的解决方案是增加一个 list存放 linked list node, 然后用dict 存放 list index. 这样就可以用连续下标访问了(顺序访问依然需要linked list, 因为list 里的node是乱序). 实际上目前的测试时间就是按这个来的.

测试 slots = () 是否可以节约内存

内存占用的话我觉得不是一个大问题. song model 只需要提供 url就可以了. linked list的reference和dict都是存放的整数, 本身都不大. 当然还需要测试一下.

所以是不是只有第二种方案可以适应

我觉得也可以考虑 lazy load 这种模式, 这样random mode就是在有限范围内的随机. 不过还没有想好. 可以继续讨论.

最后, 我只是学编程的新手, 从这个repo的代码学到了好多东西, 大佬就不敢当啦...