python-doc-tw.github.io/library/bisect.html at master · python-doc-tw/python-doc-tw.github.io

History

300 lines (271 loc) · 25.4 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"

"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<head>

<title>8.6. bisect — 陣列二分演算法 (Array bisection algorithm) — Python 3.7.0 說明文件</title>

title="在 Python 3.7.0 說明文件中搜尋"

href="../_static/opensearch.xml"/>

</head><body>

<ul>

<a href="../genindex.html" title="General Index"

accesskey="I">索引</a></li>

<a href="../py-modindex.html" title="Python 模組索引"

>模組</a> |</li>

<a href="array.html" title="8.7. array — 高效率的數值型態陣列"

accesskey="N">下一頁</a> |</li>

<a href="heapq.html" title="8.5. heapq — 堆積佇列 (heap queue) 演算法"

accesskey="P">上一頁</a> |</li>

<li><img src="../_static/py.png" alt=""

style="vertical-align: middle; margin-top: -1px"/></li>

<li><a href="https://www.python.org/">Python</a> »</li>

<li>

zh_TW

3.7.0

<a href="../index.html">Documentation </a> »

</li>

<li class="nav-item nav-item-1"><a href="index.html" >Python 標準函式庫 (Standard Library)</a> »</li>

<li class="nav-item nav-item-2"><a href="datatypes.html" accesskey="U">8. Data Types</a> »</li>

</form>

</div>

</li>

</ul>

</div>

<h1>8.6. <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-mod docutils literal notranslate">bisect</code></a> — 陣列二分演算法 (Array bisection algorithm)<a class="headerlink" href="#module-bisect" title="本標題的永久連結">¶</a></h1>

原始碼： <a class="reference external" href="https://github.com/python/cpython/tree/3.7/Lib/bisect.py">Lib/bisect.py</a>

這個模組維護一個已經排序過的 list ，當我們每次做完插入後不需要再次排序整個 list 。一個很長的 list 的比較操作很花費時間，為了改進這點，這個模組是其中一個常用的方法。這個模組被命名為 <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-mod docutils literal notranslate">bisect</code></a> 來自他使用一個基礎的 bisection 演算法實作。模組的原始碼是這個演算法的一個完善的實作（邊界條件已經是正確的了）。

此模組提供下面的函式

<code class="descclassname">bisect.</code><code class="descname">bisect_left</code>(a, x, lo=0, hi=len(a))<a class="headerlink" href="#bisect.bisect_left" title="本定義的永久連結">¶</a></dt>

<dd>在 a 當中找到一個位置，讓 x 插入後 a 仍然是排序好的。參數 lo 和 hi 用來指定 list 中應該被考慮的子區間，預設是考慮整個 list 。如果 a 裡面已經有 x 出現，插入的位置會在所有 x 的前面（左邊）。回傳值可以被當作 <code class="docutils literal notranslate">list.insert()</code> 的第一個參數，但列表 a 必須先排序過。

回傳的插入位置 i 將陣列 a 分為兩半，使得 <code class="docutils literal notranslate">all(val < x for val in a[lo:i])</code> 都在左側且 <code class="docutils literal notranslate">all(val >= x for val in a[i:hi])</code> 都在右側。

</dd></dl>

<code class="descclassname">bisect.</code><code class="descname">bisect_right</code>(a, x, lo=0, hi=len(a))<a class="headerlink" href="#bisect.bisect_right" title="本定義的永久連結">¶</a></dt>

<code class="descclassname">bisect.</code><code class="descname">bisect</code>(a, x, lo=0, hi=len(a))<a class="headerlink" href="#bisect.bisect" title="本定義的永久連結">¶</a></dt>

<dd>類似 <a class="reference internal" href="#bisect.bisect_left" title="bisect.bisect_left"><code class="xref py py-func docutils literal notranslate">bisect_left()</code></a> ，但回傳的插入位置會在所有 a 當中的 x 的後面（右邊）。

回傳的插入位置 i 將陣列 a 分為兩半，使得 <code class="docutils literal notranslate">all(val <= x for val in a[lo:i])</code> 都在左側且 <code class="docutils literal notranslate">all(val > x for val in a[i:hi])</code> 都在右側。

</dd></dl>

<code class="descclassname">bisect.</code><code class="descname">insort_left</code>(a, x, lo=0, hi=len(a))<a class="headerlink" href="#bisect.insort_left" title="本定義的永久連結">¶</a></dt>

<dd>不破壞 a 的排序下插入 x ，這等價於 <code class="docutils literal notranslate">a.insert(bisect.bisect_left(a, x, lo, hi), x)</code> ，注意 a 必須是已經排序過的 list 。注意搜尋只需要 O(log n) 時間而插入需要很慢的 O(n) 時間，這使得插入操作主導了需要的花費時間。

</dd></dl>

<code class="descclassname">bisect.</code><code class="descname">insort_right</code>(a, x, lo=0, hi=len(a))<a class="headerlink" href="#bisect.insort_right" title="本定義的永久連結">¶</a></dt>

<code class="descclassname">bisect.</code><code class="descname">insort</code>(a, x, lo=0, hi=len(a))<a class="headerlink" href="#bisect.insort" title="本定義的永久連結">¶</a></dt>

<dd>類似 <a class="reference internal" href="#bisect.insort_left" title="bisect.insort_left"><code class="xref py py-func docutils literal notranslate">insort_left()</code></a> ，但插入的位置會在所有 a 當中的 x 的後面（右邊）。

</dd></dl>

也參考

<a class="reference external" href="https://code.activestate.com/recipes/577197-sortedcollection/">SortedCollection recipe</a> that uses

bisect to build a full-featured collection class with straight-forward search

methods and support for a key-function. The keys are precomputed to save

unnecessary calls to the key function during searches.

</div>

<h2>8.6.1. Searching Sorted Lists<a class="headerlink" href="#searching-sorted-lists" title="本標題的永久連結">¶</a></h2>

The above <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-func docutils literal notranslate">bisect()</code></a> functions are useful for finding insertion points but

can be tricky or awkward to use for common searching tasks. The following five

functions show how to transform them into the standard lookups for sorted

lists:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>def index(a, x):

'Locate the leftmost value exactly equal to x'

i = bisect_left(a, x)

if i != len(a) and a[i] == x:

return i

raise ValueError

def find_lt(a, x):

'Find rightmost value less than x'

if i:

return a[i-1]

raise ValueError

def find_le(a, x):

'Find rightmost value less than or equal to x'

i = bisect_right(a, x)

if i:

return a[i-1]

raise ValueError

def find_gt(a, x):

'Find leftmost value greater than x'

if i != len(a):

return a[i]

raise ValueError

def find_ge(a, x):

'Find leftmost item greater than or equal to x'

if i != len(a):

return a[i]

raise ValueError

</pre></div>

</div>

<h2>8.6.2. Other Examples<a class="headerlink" href="#other-examples" title="本標題的永久連結">¶</a></h2>

The <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-func docutils literal notranslate">bisect()</code></a> function can be useful for numeric table lookups. This

example uses <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-func docutils literal notranslate">bisect()</code></a> to look up a letter grade for an exam score (say)

based on a set of ordered numeric breakpoints: 90 and up is an 『A』, 80 to 89 is

a 『B』, and so on:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> def grade(score, breakpoints=[60, 70, 80, 90], grades='FDCBA'):

... i = bisect(breakpoints, score)

... return grades[i]

...

>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]

['F', 'A', 'C', 'C', 'B', 'A', 'A']

</pre></div>

</div>

Unlike the <a class="reference internal" href="functions.html#sorted" title="sorted"><code class="xref py py-func docutils literal notranslate">sorted()</code></a> function, it does not make sense for the <a class="reference internal" href="#module-bisect" title="bisect: Array bisection algorithms for binary searching."><code class="xref py py-func docutils literal notranslate">bisect()</code></a>

functions to have key or reversed arguments because that would lead to an

inefficient design (successive calls to bisect functions would not 「remember」

all of the previous key lookups).

Instead, it is better to search a list of precomputed keys to find the index

of the record in question:

<div class="highlight-python3 notranslate"><div class="highlight"><pre>>>> data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]

>>> data.sort(key=lambda r: r[1])

>>> keys = [r[1] for r in data] # precomputed list of keys

>>> data[bisect_left(keys, 0)]

('black', 0)

('blue', 1)

('red', 5)

('yellow', 8)

</pre></div>

</div>

<ul>

<li><a class="reference internal" href="#">8.6. <code class="docutils literal notranslate">bisect</code> — 陣列二分演算法 (Array bisection algorithm)</a><ul>

<li><a class="reference internal" href="#searching-sorted-lists">8.6.1. Searching Sorted Lists</a></li>

<li><a class="reference internal" href="#other-examples">8.6.2. Other Examples</a></li>

</ul>

</li>

</ul>

<a href="heapq.html"

title="上一章">8.5. <code class="docutils literal notranslate">heapq</code> — 堆積佇列 (heap queue) 演算法</a>

<a href="array.html"

title="下一章">8.7. <code class="docutils literal notranslate">array</code> — 高效率的數值型態陣列</a>

<li><a href="../bugs.html">Report a Bug</a></li>

<li>

<a href="https://github.com/python/cpython/blob/3.7/Doc/library/bisect.rst"

rel="nofollow">Show Source

</a>

</li>

</ul>

</div>

</div>

<ul>

<a href="../genindex.html" title="General Index"

>索引</a></li>

<a href="../py-modindex.html" title="Python 模組索引"

>模組</a> |</li>

<a href="array.html" title="8.7. array — 高效率的數值型態陣列"

>下一頁</a> |</li>

<a href="heapq.html" title="8.5. heapq — 堆積佇列 (heap queue) 演算法"

>上一頁</a> |</li>

<li><img src="../_static/py.png" alt=""

style="vertical-align: middle; margin-top: -1px"/></li>

<li><a href="https://www.python.org/">Python</a> »</li>

<li>

zh_TW

3.7.0

<a href="../index.html">Documentation </a> »

</li>

<li class="nav-item nav-item-1"><a href="index.html" >Python 標準函式庫 (Standard Library)</a> »</li>

<li class="nav-item nav-item-2"><a href="datatypes.html" >8. Data Types</a> »</li>

</form>

</div>

</li>

</ul>

</div>

The Python Software Foundation is a non-profit corporation.

<a href="https://www.python.org/psf/donations/">Please donate.</a>

Last updated on 8月 22, 2018.

<a href="../bugs.html">Found a bug</a>?

Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.7.7.

</div>

</body>

</html>

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

bisect.html

Latest commit

History

bisect.html

File metadata and controls