是否有一个库函数在列表/元组上执行二进制搜索并返回项目的位置(如果找到)和'False'(-1,None等),如果没有？
我在bisect模块中找到了函数bisect_left/right ,但即使该项不在列表中,它们仍会返回一个位置.这对于他们的预期用途来说非常好,但我只是想知道一个项目是否在列表中(不想插入任何内容).
我想过使用bisect_left然后检查那个位置的项目是否等于我正在搜索的项目,但这看起来很麻烦(我还需要检查边界是否可以大于我列表中的最大数字).如果有一个更好的方法我想知道它.
编辑为了澄清我需要这个:我知道字典非常适合这个,但我试图尽可能降低内存消耗.我的预期用法是一种双向查找表.我在表中有一个值列表,我需要能够根据它们的索引访问这些值.而且如果值不在列表中,我希望能够找到特定值的索引或None.
使用字典是最快的方法,但会(大约)加倍内存需求.
我在问这个问题,认为我可能忽略了Python库中的某些东西.正如Moe建议的那样,我似乎必须编写自己的代码.
在Python中,如何在排序列表中找到第一个值大于阈值的索引？
我可以想到几种方法(线性搜索,手写二分法,......),但我正在寻找一种干净,合理有效的方法.由于它可能是一个非常常见的问题,我相信经验丰富的SOers可以提供帮助!
谢谢!
当我使用该bisect_left()函数时,为什么我没有得到index该元素,而是index + 1？
import bisect
t3 = ['carver', 'carvers', 'carves', 'carving', 'carvings']
print bisect.bisect(t3, 'carves') # 3
print bisect.bisect(t3, 'carving') # 4
print bisect.bisect(t3, 'carver') # 1
我需要模拟Fluxbox窗口管理器的窗口放置策略.
作为一个粗略的指南,可视化随机大小的窗口一次一个地填满屏幕,其中每个窗口的粗略大小导致屏幕上平均80个窗口,而没有任何窗口与另一个窗口重叠.
如果您的系统上安装了Fluxbox和Xterm,您可以尝试使用xwinmidiarptoy BASH脚本来查看我想要发生的事情的粗略原型.请参阅我写过的xwinmidiarptoy.txt说明,解释它的作用以及如何使用它.
重要的是要注意窗口将关闭,并且关闭先前占用的窗口的空间再次可用于放置新窗口.
该算法需要是一个在线算法处理数据"以串行方式逐个处理,即按照输入被提供给算法的顺序,而不需要从一开始就提供整个输入."
Fluxbox窗口放置策略有三个我想模拟的二元选项:
Windows构建水平行或垂直列(可能)
Windows从左到右或从右到左放置
Windows从上到下或从下到上放置
目标算法与窗口放置算法之间的差异
坐标单位不是像素.将放置块的网格将是128 x 128个单位.此外,放置区域可以通过放置在网格内的边界区域进一步收缩.
为什么算法有问题？
它需要在音频应用程序中运行到实时线程的最后期限.
此刻我只关心获得快速算法,不关心实时线程的含义以及编程带来的所有障碍.
虽然算法永远不会放置一个与另一个重叠的窗口,但是用户将能够放置和移动某些类型的块,将存在重叠的窗口.用于存储窗口和/或空闲空间的数据结构需要能够处理这种重叠.
到目前为止,我有两个选择,我已经建立了松散的原型:
1)Fluxbox放置算法的一个端口到我的代码中.
问题是,当我尝试使用该算法放置256块的最坏情况时,客户端(我的程序)被踢出音频服务器(JACK).该算法在放置第256个窗口时对已经放置的块列表执行超过14000次完整(线性)扫描.
为了演示这一点,我创建了一个名为text_boxer-0.0.2.tar.bz2的程序,该程序将文本文件作为输入并将其排列在ASCII框中.问题make来构建它.有点不友好,使用--help(或任何其他无效选项)的命令行选项列表.您必须使用该选项指定文本文件.
2)我的替代方法.
仅部分实现,该方法对矩形空闲未使用空间的每个区域使用数据结构(窗口列表可以完全分离,并且不需要用于测试该算法).数据结构充当双向链表中的节点(具有排序插入),并且包含左上角的坐标以及宽度和高度.
此外,每个块数据结构还包含四个链接,这四个链接连接到四个边中的每一个上的每个紧邻(触摸)块.
重要规则:每个块每侧只能触摸一个块.这是一种特定于算法存储空闲未使用空间的方法的规则,并且不会影响实际窗口可能相互接触的数量.
这种方法的问题是,它非常复杂.我已经实现了直接的情况,其中1)从块的一个角去除空间,2)分割相邻的块以便遵守重要的规则.
不太直接的情况,其中要移除的空间只能在一列或一排框中找到,只是部分实现 - 如果要移除的一个块完全适合宽度(即列)或高度(即然后出现问题.甚至没有提到这个事实,它只检查一个框宽的列,并排一个框高.
我已经用C语言实现了这个算法 - 我正在使用这个项目的语言(我几年没有使用过C++,在把注意力都集中在C开发之后使用它很不舒服,这是一个爱好).实现是700多行代码(包括大量空行,支撑线,注释等).该实现仅适用于水平行+左右+上下放置策略.
所以我要么添加一些方法来使这些+700行代码适用于其他7个放置策略选项,或者我将不得不为其他7个选项复制那些+700行代码.这些都不具吸引力,第一,因为现有代码足够复杂,第二,因为膨胀.
由于缺少功能,该算法甚至不能在实时最坏情况下使用它,因此我仍然不知道它实际上是否比第一种方法更好或更差.
该算法的C实现的当前状态是freespace.c.我用它gcc -O0 -ggdb freespace.c来构建,并以xterm大小运行它至少至少124 x 60个字符.
那里还有什么？
我撇去并打折: …
我有一个排序的值数组和一个值，如下所示：
x <- c(1.0, 3.45, 5.23, 7.3, 12.5, 23.45)
v <- 6.45
v我可以找到要插入的值的索引，x同时保持排序顺序：
max(which(x <= v))
[1] 3
这是漂亮而紧凑的代码，但我有一种直觉，在幕后这确实效率低下：因为which()不知道数组已排序，所以必须检查所有值。
有没有更好的方法来找到这个索引值？
注意：我对实际合并v到x. 我只想要索引值。
有没有我可以在网上找到的二分法,特别是对于python？
例如,给定这些方程式,我如何使用二分法求解它们？
x^3 = 9
3 * x^3 + x^2 = x + 5
cos^2x + 6 = x
推理:我试图在Python中实现类似的东西git bisect,但基本上是一个目录列表.
我有一个(长)版本号列表,如下所示:
['1.0', '1.14', '2.3', '3.1', '4']
我有一个函数works(),它取一个版本号,并返回一个值.
[works(x) for x in my_list]看起来像['foo', 'foo', 'foo', 'bar', 'bar']
...... :
但是跑步works()非常昂贵.
我想做一些可以找到变化边界的二等分.
假设我有一些可计算的谓词P,它将整数映射到bool.我知道这P 0是真的,我知道有些N P N是假的.我也知道这P n = false意味着P (n + 1) is false[*].我想找到最大的n,这P n是真的.
显然,我可以通过二分找到解决方案.不幸的是,评估P是昂贵的(可能需要一个小时左右).我还有一个有许多内核的闪亮服务器.
如果评估P持续时间并且我有2个线程(比方说),我可以看到我将如何进行搜索.我划分区间[a,b]上分成三段,并评估P (2a + b)/3和P (a + 2b)/3.两次评估完成后,我就会知道要归入的三个细分中的哪一个.使用两个线程,我的搜索时间将减少三分之一.优秀!
但是,如果评估P需要大量不同的时间呢？在我的具体例子中,它可能需要10秒到1个小时左右.再次假设我有2个线程并且如上所述划分了间隔.也许第一个线程(评估P (2a+b)/3)首先完成.我如何决定下一个的运行方式？
我想有一些信息理论或类似的链接,因为我正在尝试运行测试,根据我目前的知识,这将给我最多的信息.但这似乎应该是其他人调查过的问题 - 任何人都可以指出我的论文或类似内容吗？
[*]在我关心的具体情况中,测试涉及运行SMT求解器,尝试使用X≥n形式的一个额外约束找到约束问题的解X,其中n是上面的整数.
我想制作一个Python程序,它将运行二分法来确定以下的根:
f(x) = -26 + 85x - 91x2 +44x3 -8x4 + x5
二分法是用于估计多项式f(x)的根的数值方法.
我可以使用任何可用的伪代码,算法或库来告诉我答案吗？
我有这个代码:
#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;
double f(double x);
double biseccion(double a, double b, double tolerancia, int maxiter);
int main()
{
double a, b, raiz;
double tolerancia=0.00000;
int maxiter=25;
cout << "Input begin of interval: ";
cin >> a;
cout << "Input end of interval: ";
cin >> b;
cout << "\n";
cout << " # de"<<"\n"<<"Iteration"<<"\t"<<" A"<<"\t"<<" B"<<"\t"<<" C"<<"\t"<<" f(c)"<<endl;
raiz=biseccion(a,b,tolerancia,maxiter);
cout << "\n";
cout << "The root is: "<< raiz <<endl;
return 0;
} …