Warm tip: This article is reproduced from serverfault.com, please click
performance python random shuffle

Why is random.shuffle so much slower than using sorted function?

发布于 2020-11-28 01:28:46

When using pythons random.shuffle function, I noticed it went significantly faster to use sorted(l, key=lambda _: random.random()) than random.shuffle(l). As far as I understand, both ways produce completely random lists, so why does shuffle take so much longer?

Below are the times using timeit module.

from timeit import timeit
setup = 'import random\nl = list(range(1000))'

# 5.542 seconds
print(timeit('random.shuffle(l)', setup=setup, number=10000))

# 1.878 seconds
print(timeit('sorted(l, key=lambda _: random.random())', setup=setup, number=10000))
Questioner
mazore
Viewed
0
分享
ShadowRanger 2020-11-28 09:33:40

On CPython (the reference interpreter) random.shuffle is implemented in Python (and implemented in terms of _randbelow, itself a Python wrapper around getrandbits, the C level function that ultimately implements it, and which can end up being called nearly twice as often as strictly necessary in an effort to ensure the outputs are unbiased); sorted (and random.random) are implemented in C. The overhead of performing work in Python is higher than performing similar work in C.

mazore 2020-11-28 01:38:01

Why doesn't random.shuffle just return the list using sorted if it runs so much faster using C?

ShadowRanger 2020-11-28 01:41:41

@Evan: It's using a fairly painstaking algorithm that guarantees (to the limits of the PRNG) a perfect shuffle; avoiding bias is a surprisingly hard problem, and making it faster is less of a priority than making sure it's definitely correct. There have been a number of bugs in the random module that led to slight biases in output (it's why _randbelow is implemented the way it is now), and they've generally been pretty gunshy about using faster algorithms that aren't provably unbiased.

热门帖子

1
十兆宽带 100 块钱一个月我是活在 80 年代吗？
2
关于高质量 屏幕共享的问题
3
我是真的受不了打小报告的三八了！
4
怎么管理自己的文件体系
5
[开发者自荐] AirBattery: 在 Mac 端获取所有设备的电量并显示在 Dock 或状态栏上
6
南京移动 IPV6 被停
7
WireGuard 跨国组网失败后,一个新工具的诞生
8
你的 IDEA(2024.1) 在 macOS 上崩吗？
9
居家办公 兼谈普通人的无聊和解救方式
10
拼多多开始用灵动岛放广告了？

热门github

1
Implementation of paper - YOLOv9: Learning What You Want to Learn Using Programmable Gradient Information
2
A Windows and Office activator using HWID / Ohook / KMS38 / Online KMS activation methods, with a focus on open-source code and fewer antivirus detections.
3
Get up and running with Llama 2, Mistral, Gemma, and other large language models.
4
该项目可以让你通过订阅的方式使用Cloudflare WARP+，自动获取流量。This project enables you to use Cloudflare WARP+ through subscription, automatically acquiring traffic.
5
Multi functional app to find duplicates, empty folders, similar images etc.
6
Xray panel supporting multi-protocol multi-user expire day & traffic & ip limit (Vmess & Vless & Trojan & ShadowSocks & Wireguard)
7
The Free Software Media System
8
lightweight, standalone C++ inference engine for Google's Gemma models.
9
📚 Freely available programming books
10
A collective list of free APIs
11
1️⃣🐝🏎️ The One Billion Row Challenge -- A fun exploration of how quickly 1B rows from a text file can be aggregated with Java
12
🎓 Path to a free self-taught education in Computer Science!
13
Curso para aprender el lenguaje de programación Python desde cero y para principiantes. 75 clases, 37 horas en vídeo, código, proyectos y grupo de chat. Fundamentos, frontend, backend, testing, IA...
14
This repository contains System Design resources which are useful while preparing for interviews and learning Distributed Systems
15
Mamba is a new state space model architecture showing promising performance on information-dense data such as language modeling, where previous subquadratic models fall short of Transformers. It is based on the line of progress on structured state space models, with an efficient hardware-aware design and implementation in the spirit of FlashAttention.