区块链技术博客
www.b2bchain.cn

TLE计算列表中指定范围内的元素数 – python程序员分享

D0b2wT.gif

本文介绍了TLE计算列表中指定范围内的元素数 – python程序员分享,有助于帮助完成毕业设计以及求职,是一篇很好的资料。

对技术面试,学习经验等有一些体会,在此分享。

有一个未排序的列表a和一个范围列表,例如ranges = [(10, 20), (30, 50), (15, 35) ...]a中的最大值是uint64_t。目标是计算每个范围的元素数量。正常的解决方案非常直观,只需计算范围内的元素并打印结果即可。但问题是来自在线法官。我厌倦了保密的解决方案,但对于每个解决方案,OJ都给出了超过时限的限制。
a的最大长度为10,000,000,ranges的最大长度为1,000,000。
测试列表a具有1000万个随机数,而ranges具有100万对范围:

import numpy as np  a = list(np.random.randint(low=1, high=0x7fffffffffffffff, size=10_000_000))  ranges = [] for _ in range(1_000_000):     x, y = np.random.randint(low=1, high=0x7fffffffffffffff, size=2)     ranges.append((x, y) if x < y else (y, x)) 

第一个解决方案是:

import bisect  a.sort()  low_d = {} up_d = {}  def count(r):     low, up = r      if low not in low_d:         l = bisect.bisect_left(a, low)         low_d[low] = l     else:         l = low_d[low]      if up not in up_d:         u = bisect.bisect_right(a, up, lo=l)         up_d[up] = u     else:         u = up_d[up]      return u - l  result = [*map(count, ranges)] 

缺点很明显,当sort()很大时,a会非常耗时。

原始的第二个解决方案比上述解决方案要慢得多。
弃。

两种解决方案均导致TLE错误。我使用的OJ就像一个黑盒子,我不知道它用来测试程序的测试示例。
由于该程序在OJ上运行,因此不允许使用numpy
有什么方法可以优化性能?

参考方案

此C ++代码在此硬件上以1.9s运行,而-O2与我最好的Python代码13.2s相比运行(与Python中的基准测试相比,这是一个较慢的硬件)。

可能的改进:

上等分应在下等分之上搜索
使用预先计算的等分值,例如python代码
从Unisort: an Algorithm to Sort Uniformly Distributed Numbers in O(n) Time. R.T. Ionescu 2013实现Unisort算法

码:

#include <iostream> #include <string> #include <random> #include <cstdint> #include <array> #include <chrono> #include <algorithm> #include <iterator>  int tdiff(std::chrono::time_point<std::chrono::system_clock> start, std::chrono::time_point<std::chrono::system_clock> _end) {     int result;     result = (std::chrono::duration_cast<std::chrono::milliseconds>(_end - start)).count();     return result;  }  int main()  {     std::random_device rd;     std::mt19937 gen(rd());     std::uniform_int_distribution<int64_t> dis(1, 0x7fffffffffffffff);      #define A_SIZE 10000000     #define R_SIZE 1000000     std::vector<int64_t> a(A_SIZE);     int a_size = A_SIZE;     int r_size = R_SIZE;     for (int i=0; i<a_size; i++){         a[i] = dis(gen);     }     std::vector<std::vector<int64_t>> ranges1(R_SIZE, std::vector<int64_t>(2));      int64_t x,y;     for (int i=0; i<ranges1.size(); i++){         x = dis(gen);         y = dis(gen);         if (x < y){             ranges1[i] = {x,y};         }else{             ranges1[i] = {y,x};         }     }     std::chrono::time_point<std::chrono::system_clock> start, _end;      start = std::chrono::system_clock::now();     std::sort(a.begin(), a.end());     std::vector<int64_t> counts(A_SIZE);     std::vector<int64_t>::iterator l;     std::vector<int64_t>::iterator u;     for (int i=0; i<r_size; i++){         l = std::lower_bound(a.begin(),a.end(),ranges1[i][0]);         u = std::upper_bound(a.begin(),a.end(),ranges1[i][1]);         counts[i] = (int64_t)std::distance(l,u);     }     _end = std::chrono::system_clock::now();     std::cout << tdiff(start, _end) << "n";      std::cout << counts[0] << "n";     return 0; } 

Python Pandas导出数据 – python

我正在使用python pandas处理一些数据。我已使用以下代码将数据导出到excel文件。writer = pd.ExcelWriter('Data.xlsx'); wrong_data.to_excel(writer,"Names which are wrong", index = False); writer.…

Python 3运算符>>打印到文件 – python

我有以下Python代码编写项目的依赖文件。它可以在Python 2.x上正常工作,但是在使用Python 3进行测试时会报告错误。depend = None if not nmake: depend = open(".depend", "a") dependmak = open(".depend.mak&#…

Python:对于长时间运行的进程,通过还是休眠? – python

我正在编写一个队列处理应用程序,该应用程序使用线程等待和响应要发送到该应用程序的队列消息。对于应用程序的主要部分,只需要保持活动状态即可。对于像这样的代码示例:而True: 通过要么而True: time.sleep(1)哪一个对系统的影响最小?除了保持python应用运行外,什么都不做的首选方式是什么? 参考方案 我可以想象time.sleep()会减少系…

如何使用BeautifulSoup在<tr>中捕获特定的<td> – python

尝试从nyc Wiki页面中的高中列表中获取所有高中名称。我已经写了足够多的脚本,可以让我获取包含在高中,学业和入学条件列表的表的<tr>标记中的所有信息-但是我如何才能缩小到我认为的范围内在td[0]内休息(会弹出KeyError)-只是学校的名称?到目前为止我写的代码:from bs4 import BeautifulSoup from ur…

Python NotImplemented常数 – python

浏览decimal.py,它在许多特殊方法中使用NotImplemented。例如class A(object): def __lt__(self, a): return NotImplemented def __add__(self, a): return NotImplemented Python docs say: 未实现 可以通过“丰富比较”返回的特…

部分转自互联网,侵权删除联系

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » TLE计算列表中指定范围内的元素数 – python程序员分享
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们