专栏首页Apache IoTDB查找表(Lookup table)

查找表(Lookup table)

查找表(look-up-table)这个名字很好听,缩写 LUT,听起来很高端,其实是一种很简单高效的索引操作,今天简单介绍一下。

是啥

wiki定义:

a lookup table is an array that replaces runtime computation with a simpler array indexing operation

翻译一下:

查找表就是一个数组,用来替代计算,加速查询的索引操作。

举个例子,以前我们算对数基本都需要计算器,很多时候数学考试不让带计算器,只给你一个表来查,最大的优点就是节约时间。

计算机中很多概念都是来源于生活。因此把这种需要复杂计算的操作提前计算好,保存到一个数组里,用的时候不需要重新计算,直接查表,这就是查找表,典型的以空间换时间。

举一个在数组查询中用到的例子:

首先看第二行,我有一堆01数字的数组,在这个数组上的需要执行一个操作:查看某个位置之前有几个1。没有额外结构时,每次给一个位置,就需要从开头遍历,逐个判断是不是 1,时间复杂度O(N)。

下面引入第一行的查找表。提前将数据按固定长度分组,这里 5 个一组,并计算每组的起始位置之前有几个 1。这样,再给我一个下标 n=11,可以先计算 下取整(n/5)=2 ,然后找到查找表位置为 2 的值为 7,再从原始数组上查找 下标从 2*5=10 到 11位置,共有 1 个 1。这样,总的返回值就是 8 。

通过这样一个简单的查找表,将这个操作的时间降为了常数项。

基本原理就是这!

总结

查找表本质上是用 “预计算+空间” 换取 “时间” 的一种索引技术,效率很高。如果程序中有经常需要重复计算操作,且结果的空间占用不大,可以考虑使用查找表替换掉。

本文分享自微信公众号 - IoTDB漫游指南(Apache-IoTDB),作者:铁头乔

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-12

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Apache IoTDB 系列教程-3:部署运维

    IoTDB 的理念就是系统运维要简单,要一键启动、开箱即用。就从启动开始说起吧,需要安装 jdk8 或者 jdk11,下载发布版,http://iotdb.ap...

    Apache IoTDB
  • Apache IoTDB 系列教程-5:常见问题汇总(1)

    汇总:启动问题、连接问题、负载过大、路径名问题、group by 语法、精度损失、元数据为空。

    Apache IoTDB
  • 数据库漫游指南

    “文艺复兴以降,源远流长的科学精神和逐步形成的学术规范......你们这一脸迷茫的看着我,不知道我在说什么吗?这是机械工业出版社的前言!多么经典的书,回去好好看...

    Apache IoTDB
  • 第三十五课 如何配置Metadata以便装饰你的ERC721非同质化资产?

    前面2课讲解了如何部署ERC721非同质化资产,并作为海洋商店发布在OpenSea测试网络。 本文以野狼队的队员TOKEN为例,讲解如何配置图形/文字特有的E...

    辉哥
  • WPF小坑第十八篇之VS2019使用EF6小坑

    原来一直操作数据库都是直接二话不说,上来就是先来一个SQL的Helper,然后再根据具体的业务需求编写相应的SQL语句,然后转为成对象再进行各种操作;这不猿妹子...

    WPF程序员
  • 全国二级C知识点总结7-编译预处理、文件

    l int argc是命令行中的字符串数,char *argv[]是指向字符串的指针数组,系统使用空格把各个字符串隔开。

    用户6755376
  • SAP CRM系统订单模型的设计与实现

    SAP成都研究院的一个部门领导让我给他的团队做一个SAP CRM One Order框架的培训,这是我准备的培训内容。

    Jerry Wang
  • Mysql业务设计(物理设计)

    列如:对于表、表的名称应该能体现表中存储的数据内容,对于存储过程存储过程应该能够体现存储过程的功能。

    彼岸舞
  • 小兴逛Google I/O 2017(day1实况)

    陈志兴,Google I/O 2017大会的小时光茶社特派员 ,腾讯SNG增值产品部内容中心Android组leader,主要负责手Q个性化业务、手Q WebV...

    小时光
  • Linux 后台运行 Jar 包

    在部署 Java 程序的时候,最简单的方式就打成 jar 并使用 java -jar xxxx.jar 运行,但是如果是一台 Linux 服务器,执行远程上去之...

    zucchiniy

扫码关注云+社区

领取腾讯云代金券