精华内容
下载资源
问答
  • 2020-09-30 21:29:12

    如何在1亿个数中找出最大的100个数(top K问题)

    ​ 最容易想到的方法是将数据全部排序,然后在排序后的集合中进行查找,最快的排序算法的时间复杂度一般为O(nlogn),如快速排序。但是在32位的机器上,每个float类型占4个字节,1亿个浮点数就要占用400MB的存储空间,对于一些可用内存小于400M的计算机而言,很显然是不能一次将全部数据读入内存进行排序的。其实即使内存能够满足要求(我机器内存都是8GB),该方法也并不高效,因为题目的目的是寻找出最大的10000个数即可,而排序却是将所有的元素都排序了,做了很多的无用功。

    ​ 第二种方法为局部淘汰法,该方法与排序方法类似,用一个容器保存前10000个数,然后将剩余的所有数字——与容器内的最小数字相比,如果所有后续的元素都比容器内的10000个数还小,那么容器内这个10000个数就是最大10000个数。如果某一后续元素比容器内最小数字大,则删掉容器内最小元素,并将该元素插入容器,最后遍历完这1亿个数,得到的结果容器中保存的数即为最终结果了。此时的时间复杂度为O(n+m^2),其中m为容器的大小,即10000。

    ​ 第三种方法是分治法,将1亿个数据分成100份,每份100万个数据,找到每份数据中最大的10000个,最后在剩下的10010000个数据里面找出最大的10000个。如果100万数据选择足够理想,那么可以过滤掉1亿数据里面99%的数据。100万个数据里面查找最大的10000个数据的方法如下:用快速排序的方法,将数据分为2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大堆个数N小于10000个,就在小的那堆里面快速排序一次,找第10000-n大的数字;递归以上过程,就可以找到第1w大的数。参考上面的找出第1w大数字,就可以类似的方法找到前10000大数字了。此种方法需要每次的内存空间为10^64=4MB,一共需要101次这样的比较。*

    ​ 第四种方法是Hash法。如果这1亿个书里面有很多重复的数,先通过Hash法,把这1亿个数字去重复,这样如果重复率很高的话,会减少很大的内存用量,从而缩小运算空间,然后通过分治法或最小堆法查找最大的10000个数。

    ​ 第五种方法采用最小堆。首先读入前10000个数来创建大小为10000的最小堆,建堆的时间复杂度为O(mlogm)(m为数组的大小即为10000),然后遍历后续的数字,并于堆顶(最小)数字进行比较。如果比最小的数小,则继续读取后续数字;如果比堆顶数字大,则替换堆顶元素并重新调整堆为最小堆。整个过程直至1亿个数全部遍历完为止。然后按照中序遍历的方式输出当前堆中的所有10000个数字。该算法的时间复杂度为O(nmlogm),空间复杂度是10000(常数)。

    实际运行:

    ​ 实际上,最优的解决方案应该是最符合实际设计需求的方案,在时间应用中,可能有足够大的内存,那么直接将数据扔到内存中一次性处理即可,也可能机器有多个核,这样可以采用多线程处理整个数据集。

    ​ 下面针对不容的应用场景,分析了适合相应应用场景的解决方案。

    (1)单机+单核+足够大内存
    ​ 如果需要查找10亿个查询次(每个占8B)中出现频率最高的10个,考虑到每个查询词占8B,则10亿个查询次所需的内存大约是10^9 * 8B=8GB内存。如果有这么大内存,直接在内存中对查询次进行排序,顺序遍历找出10个出现频率最大的即可。这种方法简单快速,使用。然后,也可以先用HashMap求出每个词出现的频率,然后求出频率最大的10个词。

    (2)单机+多核+足够大内存
    ​ 这时可以直接在内存总使用Hash方法将数据划分成n个partition,每个partition交给一个线程处理,线程的处理逻辑同(1)类似,最后一个线程将结果归并。

    ​ 该方法存在一个瓶颈会明显影响效率,即数据倾斜。每个线程的处理速度可能不同,快的线程需要等待慢的线程,最终的处理速度取决于慢的线程。而针对此问题,解决的方法是,将数据划分成c×n个partition(c>1),每个线程处理完当前partition后主动取下一个partition继续处理,知道所有数据处理完毕,最后由一个线程进行归并。

    (3)单机+单核+受限内存
    ​ 这种情况下,需要将原数据文件切割成一个一个小文件,如次啊用hash(x)%M,将原文件中的数据切割成M小文件,如果小文件仍大于内存大小,继续采用Hash的方法对数据文件进行分割,知道每个小文件小于内存大小,这样每个文件可放到内存中处理。采用(1)的方法依次处理每个小文件。

    (4)多机+受限内存
    ​ 这种情况,为了合理利用多台机器的资源,可将数据分发到多台机器上,每台机器采用(3)中的策略解决本地的数据。可采用hash+socket方法进行数据分发。

    ​ 从实际应用的角度考虑,(1)(2)(3)(4)方案并不可行,因为在大规模数据处理环境下,作业效率并不是首要考虑的问题,算法的扩展性和容错性才是首要考虑的。算法应该具有良好的扩展性,以便数据量进一步加大(随着业务的发展,数据量加大是必然的)时,在不修改算法框架的前提下,可达到近似的线性比;算法应该具有容错性,即当前某个文件处理失败后,能自动将其交给另外一个线程继续处理,而不是从头开始处理。

    ​ top K问题很适合采用MapReduce框架解决,用户只需编写一个Map函数和两个Reduce 函数,然后提交到Hadoop(采用Mapchain和Reducechain)上即可解决该问题。具体而言,就是首先根据数据值或者把数据hash(MD5)后的值按照范围划分到不同的机器上,最好可以让数据划分后一次读入内存,这样不同的机器负责处理不同的数值范围,实际上就是Map。得到结果后,各个机器只需拿出各自出现次数最多的前N个数据,然后汇总,选出所有的数据中出现次数最多的前N个数据,这实际上就是Reduce过程。对于Map函数,采用Hash算法,将Hash值相同的数据交给同一个Reduce task;对于第一个Reduce函数,采用HashMap统计出每个词出现的频率,对于第二个Reduce 函数,统计所有Reduce task,输出数据中的top K即可。

    ​ 直接将数据均分到不同的机器上进行处理是无法得到正确的结果的。因为一个数据可能被均分到不同的机器上,而另一个则可能完全聚集到一个机器上,同时还可能存在具有相同数目的数据。

    以下是一些经常被提及的该类问题。

    (1)有10000000个记录,这些查询串的重复度比较高,如果除去重复后,不超过3000000个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。请统计最热门的10个查询串,要求使用的内存不能超过1GB。

    (2)有10个文件,每个文件1GB,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。按照query的频度排序。

    (3)有一个1GB大小的文件,里面的每一行是一个词,词的大小不超过16个字节,内存限制大小是1MB。返回频数最高的100个词。

    (4)提取某日访问网站次数最多的那个IP。

    (5)10亿个整数找出重复次数最多的100个整数。

    (6)搜索的输入信息是一个字符串,统计300万条输入信息中最热门的前10条,每次输入的一个字符串为不超过255B,内存使用只有1GB。

    (7)有1000万个身份证号以及他们对应的数据,身份证号可能重复,找出出现次数最多的身份证号。

    重复问题
    ​ 在海量数据中查找出重复出现的元素或者去除重复出现的元素也是常考的问题。针对此类问题,一般可以通过位图法实现。例如,已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

    ​ 本题最好的解决方法是通过使用位图法来实现。8位整数可以表示的最大十进制数值为99999999。如果每个数字对应于位图中一个bit位,那么存储8位整数大约需要99MB。因为1B=8bit,所以99Mbit折合成内存为99/8=12.375MB的内存,即可以只用12.375MB的内存表示所有的8位数电话号码的内容。

    算法一:冒泡排序法

    千里之行,始于足下。我们先不说最好,甚至不说好。我们只问,如何“从10000个整数中找出最大的10个”?我最先想到的是用冒泡排序的办法:我们从头到尾走10趟,自然会把最大的10个数找到。方法简单,就不再这里写代码了。这个算法的复杂度是10N(N=10000)。

    算法二:

    有没有更好一点的算法呢?当然。维持一个长度为10的降序数组,每一个从数组拿到的数字都与这个降序数组的最小值比较。如果小于最小值,就舍弃;如果大于最小值,就把它插入到降序数组中的合适位置,舍弃原来的最小值。这样,遍历一遍就可以找到最大的10个数。因为需要在降序数组中插入一个数,对于遍历的每个数可能都需要这样,所以其复杂为5N。

    伪代码如下:

      A[N],a[m](分别为原始数组和降序数组,其中N=10000,m=10)
    
      a = A[0 ... 9](将数组A的前10个数赋给数组a)
    
      sort a(将组数a降序排序)
    
      for i in A[ 10 ... N](从10到N遍历数组A)
    
        if A[i] > a[9] then (如果当前值比降序数组中的最小值大)
    
          删除a[9]
    
          将A[i]插入a的合适位置,使a保持降序
    
        end if
    
      end for
    
      输出数组a
    
    

    其实算法二还有一个优点,就是当数组很大时,可以将数据分段读入内存处理,而这样做并不影响结果。

    1、首先一点,对于海量数据处理,思路基本上是确定的,必须分块处理,然后再合并起来。

    2、对于每一块必须找出10个最大的数,因为第一块中10个最大数中的最小的,可能比第二块中10最大数中的最大的还要大。

    3、分块处理,再合并。也就是Google MapReduce 的基本思想。Google有很多的服务器,每个服务器又有很多的CPU,因此,100亿个数分成100块,每个服务器处理一块,1亿个数分成100块,每个CPU处理一块。然后再从下往上合并。注意:分块的时候,要保证块与块之间独立,没有依赖关系,否则不能完全并行处理,线程之间要互斥。另外一点,分块处理过程中,不要有副作用,也就是不要修改原数据,否则下次计算结果就不一样了。

    4、上面讲了,对于海量数据,使用多个服务器,多个CPU可以并行,显著提高效率。对于单个服务器,单个CPU有没有意义呢?

    也有很大的意义。如果不分块,相当于对100亿个数字遍历,作比较。这中间存在大量的没有必要的比较。可以举个例子说明,全校高一有100个班,我想找出全校前10名的同学,很傻的办法就是,把高一100个班的同学成绩都取出来,作比较,这个比较数据量太大了。应该很容易想到,班里的第11名,不可能是全校的前10名。也就是说,不是班里的前10名,就不可能是全校的前10名。因此,只需要把每个班里的前10取出来,作比较就行了,这样比较的数据量就大大地减少了。

    之前看到一个面试题,1000个乱序正整数中找出10个最小值,要求高效快速,不能使用API。

    ​ 这学期学了些排序的方法,什么快速排序啊,冒泡啊,归并排序啊之类的。看到这个题的时候,第一反应是快速排序,因为它的名字叫快速嘛,应该够快吧。然后又想到这个题目不是要你完整的排序,只需要求出最小的10个就够了,那么冒泡法呢?冒泡法只冒前面10个数?

    ​ 发现这样子还是要遍历比较1000*10次。

    ​ 然后,利用类似于数据结构里的栈的特性?把这1000个数的前10个放到一个数组中,排好序,然后,剩下的990个数字,每个都与这10个数的最大数比较,大于则不考虑,小于就把最大值拿出来,把这个数放进去,这样的话,冒泡排序的比较次数就变成了990次,好像高效很多哦?

    更多相关内容
  • 1、Neo4j的基本使用 1.1 下载和安装Neo4j 1.2 Neo4j配置 1.2.1 核心数据文件的位置 1.2.2 安全验证,默认是启用的 1.2.3 配置JAVA 堆内存的大小 1.3 网络连接配置 1.3.1 Neo4j支持三种网络协议(Protocol) ...

    目录

    0、前言

    1、Neo4j的基本使用

    1.1 下载和安装Neo4j

    1.2 Neo4j配置

    1.2.1 核心数据文件的位置

    1.2.2 安全验证,默认是启用的

    1.2.3 配置JAVA 堆内存的大小

    1.3 网络连接配置

    1.3.1 Neo4j支持三种网络协议(Protocol)

    1.3.2 连接器的可选属性

    1.3.3 设置默认的监听地址

    1.3.4 分别设置各个网络协议的监听地址和端口

    1.4 启动Neo4j程序

    1.4.1 通过控制台启动Neo4j程序

    1.4.2 把Neo4j安装为服务(Windows Services)

    1.4.3 打开Neo4j集成的浏览器

    2、史上规模最大的中文知识图谱

    2.1 知识图谱开源Github项目

    2.1.1 解压后查看知识图谱规模:

    2.1.2 查看知识图谱数据:

    2.1.3 使用python进行读取测试:

    2.1.4 数据下载方式:

    3、将1.4亿的三元组数据文件导入Neo4j

    3.1 数据解析

    3.2 数据处理

    3.3 三元组导入前准备

    3.4 生成节点与关系csv文件

    3.4.1 选取前1000条数据作为样本数据

    3.4.2 将样本数据处理成节点和关系csv文件

    3.4.3 生成知识图谱库

    3.4.4 查看知识图谱

    3.4.5 知识图谱可视化展示

    4、总结

    4.1 Cypher查询语言

    4.2 问答机器人

    4.3 服务器端部署

     


    0、前言

    本文主要介绍如何使用Neo4j图形数据库,以及如何通过三元组数据构建知识图谱。重点介绍了目前国内最大的开源中文知识图谱ownthink,如何将ownthink的三元组源数据制作成一个知识图谱供大家使用,希望大家站在巨人的肩膀之上,构建自己的知识图谱,同时贡献一份自己的力量。

    ownthink知识图谱是一个通用的知识库,大家可以借助这种思想和构建方式来搭建专业领域的知识库,知识图谱可以应用于知识查询、机器人问答系统、知识推荐等,希望大家能够各取所需,取长补短,发挥出知识图谱的力量!

    1、Neo4j的基本使用

    1.1 下载和安装Neo4j

    1. 安装Java JDK
    2. 下载Neo4j安装文件
    3. 创建系统环境变量

    该过程属于基本操作,不详述,具体参考:NEO4J的安装配置及使用总结

    1.2 Neo4j配置

    配置文档存储在conf目录下,Neo4j通过配置文件neo4j.conf控制服务器的工作。默认情况下,不需要进行任意配置,就可以启动服务器。

    1.2.1 核心数据文件的位置

    例如,核心数据文件存储的位置,默认是在data/graph.db目录中,要改变默认的存储目录,可以更新配置选项:

    # The name of the database to mount
    #dbms.active_database=graph.db
    
    # Paths of directories in the installation.
    #dbms.directories.data=data
    

    1.2.2 安全验证,默认是启用的

    # Whether requests to Neo4j are authenticated.
    # To disable authentication, uncomment this line
    #dbms.security.auth_enabled=false

    1.2.3 配置JAVA 堆内存的大小

    # Java Heap Size: by default the Java heap size is dynamically calculated based on available system resources.
    # Uncomment these lines to set specific initial and maximum heap size.
    #dbms.memory.heap.initial_size=512m
    #dbms.memory.heap.max_size=512m

    1.3 网络连接配置

    1.3.1 Neo4j支持三种网络协议(Protocol)

    Neo4j支持三种网络协议(Protocol),分别是Bolt,HTTP和HTTPS,默认的连接器配置有三种,为了使用这三个端口,需要在Windows防火墙中创建Inbound Rules,允许通过端口7687,7474和7473访问本机

    1.3.2 连接器的可选属性

    listen_address:设置Neo4j监听的链接,由两部分组成:IP地址和端口号(Port)组成,格式是:<ip-address>:<port-number>

    1.3.3 设置默认的监听地址

    设置默认的网络监听的IP地址,该默认地址用于设置三个网络协议(Bolt,HTTP和HTTPs)的监听地址,即设置网络协议的属性:listen_address地址。在默认情况下,Neo4j只允许本地主机(localhost)访问,要想通过网络远程访问Neo4j数据库,需要修改监听地址为 0.0.0.0,这样设置之后,就能允许远程主机的访问。

    # With default configuration Neo4j only accepts local connections.
    # To accept non-local connections, uncomment this line:
    dbms.connectors.default_listen_address=0.0.0.0

    1.3.4 分别设置各个网络协议的监听地址和端口

    HTTP链接器默认的端口号是7474,Bolt链接器默认的端口号是7687,必须在Windows 防火墙中允许远程主机访问这些端口号。

    # Bolt connector
    dbms.connector.bolt.enabled=true
    #dbms.connector.bolt.tls_level=OPTIONAL
    #dbms.connector.bolt.listen_address=0.0.0.0:7687
    
    # HTTP Connector. There must be exactly one HTTP connector.
    dbms.connector.http.enabled=true
    #dbms.connector.http.listen_address=0.0.0.0:7474
    
    # HTTPS Connector. There can be zero or one HTTPS connectors.
    #dbms.connector.https.enabled=true
    #dbms.connector.https.listen_address=0.0.0.0:7473

    1.4 启动Neo4j程序

    1.4.1 通过控制台启动Neo4j程序

    点击组合键:Windows+R,输入cmd,启动DOS命令行窗口,切换到主目录,以管理员身份运行命令:

    ./neo4j.bat console

    1.4.2 把Neo4j安装为服务(Windows Services)

    安装和卸载服务:

    bin\neo4j install-service
    bin\neo4j uninstall-service

    启动服务,停止服务,重启服务和查询服务的状态:

    ./neo4j.bat start
    ./neo4j.bat stop
    ./neo4j.bat restart
    ./neo4j.bat status

    1.4.3 打开Neo4j集成的浏览器

    Neo4j服务器具有一个集成的浏览器,在一个运行的服务器实例上访问 “http://localhost:7474/”,打开浏览器,显示启动页面

    默认的host是bolt://localhost:7687,默认的用户是neo4j,其默认的密码是:neo4j,第一次成功登陆到Neo4j服务器之后,需要重置密码。访问Graph Database需要输入身份验证,Host是Bolt协议标识的主机。


    2、史上规模最大的中文知识图谱

    2.1 知识图谱开源Github项目

    GitHub 有一个开源项目,叫做 KnowledgeGraphData,号称是史上规模最大的中文知识图谱,有 1.4 亿条数据。

    知识就是力量,知识图谱是人工智能新时代的产物,简单地说知识图谱就是通过关联关系将知识组成网状的结构,然后我们的人工智能可以通过这个图谱来认识其代表的这一个现实事件,这个事件可以是现实,也可以是虚构的。

    知识图谱可以应用于机器人问答系统,知识推荐等等,下图为知识图谱在机器人上的应用。

    本次ownthink开源了史上最大规模的中文知识图谱,数据是以(实体、属性、值),(实体、关系、实体)混合的形式组织,数据格式采用csv格式,下载链接见文末。

    2.1.1 解压后查看知识图谱规模:

    $ wc -l ownthink_v2.csv
    140919781 ownthink_v2.csv

    2.1.2 查看知识图谱数据:

    $ head ownthink_v2.csv
    实体,属性,值
    胶饴,描述,别名: 饴糖、畅糖、畅、软糖。
    词条,描述,词条(拼音:cí tiáo)也叫词目,是辞书学用语,指收列的词语及其释文。
    词条,标签,文化
    红色食品,描述,红色食品是指食品为红色、橙红色或棕红色的食品。
    红色食品,中文名,红色食品
    红色食品,是否含防腐剂,否
    红色食品,主要食用功效,预防感冒,缓解疲劳
    红色食品,适宜人群,全部人群
    红色食品,用途,增强表皮细胞再生和防止皮肤衰老

    2.1.3 使用python进行读取测试:

    import sys
    import csv
    
    with open('ownthink_v2.csv', 'r', encoding='utf8') as fin:
      reader = csv.reader(fin)
      for index, read in enumerate(reader):
        print(read)
        
        if index > 10:
          sys.exit(0)

    运行以上脚本输出结果:

    ['实体', '属性', '值']
    ['胶饴', '描述', '别名: 饴糖、畅糖、畅、软糖。']
    ['词条', '描述', '词条(拼音:cí tiáo)也叫词目,是辞书学用语,指收列的词语及其释文。']
    ['词条', '标签', '文化']
    ['红色食品', '描述', '红色食品是指食品为红色、橙红色或棕红色的食品。']
    ['红色食品', '中文名', '红色食品']
    ['红色食品', '是否含防腐剂', '否']
    ['红色食品', '主要食用功效', '预防感冒,缓解疲劳']
    ['红色食品', '适宜人群', '全部人群']
    ['红色食品', '用途', '增强表皮细胞再生和防止皮肤衰老']
    ['红色食品', '标签', '非科学']
    ['红色食品', '标签', '生活']

    2.1.4 数据下载方式:

    注:解压密码是:https://www.ownthink.com/

    3、将1.4亿的三元组数据文件导入Neo4j

    开放的中文知识图谱网站:http://openkg.cn/,这个网站里有很多通用知识图谱。尤其是网站整合的ownthikhttps://kg.ownthink.com/还可以进行可视化检索。

    3.1 数据解析

    下载下来的压缩包1.94G,解压后7.98G,只有一个名为ownthink_v2.csv文件。这么大的txt文件,必须要用一些工具才能打开,普通的txt游览器,包括notepad都是打不开的,可以使用了PilotEdit来打开。

    可以看到,都是一些文本三元组格式。

    经过尝试,发现必须使用neo4j-admin import命令才能导入。LOAD CSV等都是不行的,import用时1h,LOAD CSV可能要500小时。而neo4j-admin需要一个实体csv(entity.csv),和一个关系csv(Relationship.csv)。

    参考这个https://blog.csdn.net/paopaopotter/article/details/81779575

    实体csv可以有2个,但我们只需要一个就够了。其中entity.csv的格式必须有:ID,name,:LABLE三个字段。而relationship.csv必须有:START_ID,:END_ID,name,:TYPE四个字段。如下:

    3.2 数据处理

    首先数据并不是标准的csv格式,csv格式使用逗号做分隔符,而这里使用的是\t。其次数据中有很多项是缺失的,这将导致导入失败。最后,txt中的三元组格式也不符合导入的要求。

    如此大的文本,想要一次性加载入内存然后进行处理显然也不是正确的处理方式。在网上找到一些处理三元组为entity.csv和relationship.csv的python代码,但是代码是整个读入文件,然后使用map函数,我认为这样做不行,就没试了,不然等半天报一个Out of Memory就不好了。

    首先一行一行的读入,把空值所在的行都删掉,写入一个新的CSV中,进行去空处理。然后编写脚本进行处理。

    把左右实体都给他一个唯一的ID,如entity1、entity2....,并在CSV文件里写入对应关系就行了。

    如:

    姚明  英文名 YaoMing
    姚明  性别  男
    姚明  民族  汉
    周润发 职业  演员
    周润发 出生地  香港

    变为:entity.csv

    :ID,name,:LABLE
    entity0,姚明,ENTITY
    entity1,周润发,ENTITY
    entity2,YaoMing,ENTITY1
    entity3,男,ENTITY1
    entity4,汉,ENTITY1
    entity5,演员,ENTITY1
    entity6,香港,ENTITY1

    relationship.csv

    :START_ID,name,:END_ID,:TYPE
    entity0,英文名,entity2,RELATIONSHIP
    entity0,性别,entity3,RELATIONSHIP
    entity0,民族,entity4,RELATIONSHIP
    entity1,职业,entity5,RELATIONSHIP
    entity1,出生地,entity6,RELATIONSHIP

    3.3 三元组导入前准备

    语句插入往往非常缓慢,当需要插入大量三元组时考虑使用Neo4j-import的方式。
    这种方式有许多注意点

    # 三元组数据导入前的准备工作
    1、传入文件名的时候务必使用绝对路径。
    2、在执行指令之前务必保证Neo4j处于关闭状态,如果不确定可以在Neo4j根目录下运行./bin/neo4j status 查看当前状态。
    3、使用neo4j-admin import指令导入之前先将原数据库从neo4j_home/data/databases/graph.db/中移除。
    4、写CSV文件的时候务必确保所有的节点的CSV文件的ID fileds的值都唯一、不重复。并且确保所有的边的CSV文件的START_ID 和 END_ID都包含在节点CSV文件中。
    

    3.4 生成节点与关系csv文件

    由于ownthink.csv文件太大,如果在个人电脑上至少需要预留几十个G,同时处理时间会比较长,因此,这里我从源数据中提取了前1000条作为演示案例,在win10电脑上实现整个知识图谱的构建过程。同时,对于全量数据处理的代码也一并在代码中注释说明。

    3.4.1 选取前1000条数据作为样本数据

    # -*- coding: utf-8 -*-
    # -------------------------------
    # Name:readData.py
    # Author:Nieson
    # Date:2019-10-25 16:03
    # -------------------------------
    
    import sys
    import csv
    
    filePath = "D:\\Workspace\\dataware\\ownthink_v2\\ownthink_v2.csv"
    with open(filePath, "r", encoding="utf-8") as csvFile:
        reader = csv.reader(csvFile)
        for index, read in enumerate(reader):
            f = open('csvTest.csv', 'a+', encoding='utf-8', newline='')
            csv_writer = csv.writer(f, delimiter='\t')
            write = csv_writer.writerow(read)
            print(read)
            if index > 1000:
                sys.exit(0)
            f.close()

    3.4.2 将样本数据处理成节点和关系csv文件

    # -*- coding: utf-8 -*-
    # -------------------------------
    # Name:dataProcessing.py
    # Author:Nieson
    # Date:2019-10-25 17:31
    # -------------------------------
    
    import pandas as pd
    import csv
    
    filePath = "D:\\Workspace\\dataware\\ownthink_v2\\ownthink_v2.csv"
    
    # 读取三元组文件
    n_r_b_name = [":START_ID", "relationship", ":END_ID"]
    n_r_b = pd.read_csv("csvTrain.csv", sep='\t', names=n_r_b_name)  # 使用少量的测试数据
    # n_r_b = pd.read_csv(filePath, sep=',', names=n_r_b_name)  # 使用全量的数据
    print(n_r_b.info())
    print(n_r_b.head())
    
    # 去除重复实体
    entity = set()
    entity_n = n_r_b[':START_ID'].tolist()
    entity_b = n_r_b[':END_ID'].tolist()
    for i in entity_n:
        entity.add(i)
    for i in entity_b:
        entity.add(i)
    # print(entity)
    
    # 保存节点文件-entity.csv
    csvf_entity = open("entity.csv", "w", newline='', encoding='utf-8')
    w_entity = csv.writer(csvf_entity)
    # 实体ID,要求唯一,名称,LABEL标签,可自己不同设定对应的标签
    w_entity.writerow(("entity:ID", "name", ":LABEL"))
    entity = list(entity)
    entity_dict = {}
    for i in range(len(entity)):
        w_entity.writerow(("e" + str(i), entity[i], "my_entity"))
        entity_dict[entity[i]] = "e"+str(i)
    csvf_entity.close()
    
    # 生成关系文件-relationship.csv
    # 起始实体ID,终点实体ID,要求与实体文件中ID对应,:TYPE即为关系
    n_r_b[':START_ID'] = n_r_b[':START_ID'].map(entity_dict)
    n_r_b['name'] = n_r_b['relationship']
    n_r_b[':END_ID'] = n_r_b[':END_ID'].map(entity_dict)
    n_r_b[":TYPE"] = n_r_b['relationship']
    n_r_b.pop('relationship')
    n_r_b.to_csv("relationship.csv", index=False)
    

    3.4.3 生成知识图谱库

    # 1、停止neo4j服务
    neo4j stop
    
    # 2、neo4j安装目录下databases文件中,删除默认的数据库graph.db,可以在conf文件的neo4j.conf中修改默认数据库,我的安装目录为D:\Program Files\neo4j-community-3.4.6\data\databases
    
    # 3、执行节点和关系文件导入officegraph.db数据库(我的默认数据库)
    neo4j-admin import --mode csv --database officegraph.db --nodes  "D:\\Workspace\\PycharmProjects\\officeRobot\\NiesonTest\\entity.csv" --relationships "D:\\Workspace\\PycharmProjects\\officeRobot\\NiesonTest\\relationship.csv"

     

    结果显示导入了841个节点(因为1000原数据中的节点有重复的),1002个关系(实际数据条数为1002),1682个属性值。

    3.4.4 查看知识图谱

    知识图谱生成后,重启Neo4j服务:

    neo4j start

    查看整个知识图谱,使用查询命令:

    match(n) return n

    查询实体节点为Google的所有对应的关系:

    match(n:my_entity)-[r]->(b) where n.name='Google' return n,r,b

    3.4.5 知识图谱可视化展示

    最后可以使用一些开源展示的工具(TODO),就可以进行交互和展示了:https://github.com/jexp/neo4j-3d-force-graph

    4、总结

    以上就是关于Neo4j的基本使用方式,以及如何使用三元组数据构建知识图谱的整个过程,还算是很详细细致了,大家跟着我的教程,应该能够搭建好自己的知识图谱。

    不过,凡是不能够一言而尽,本篇博文还有几个地方没有详细的介绍和探讨,这里抛出了几个方向,供有志于继续学习的小伙伴们继续思考和深入学习!

    4.1 Cypher查询语言

    在Neo4j是使用CQL进行查询,也就是Cypher查询语言,像Oracle数据库具有查询语言SQL,Neo4j具有CQL作为查询语言。

    Neo4j CQL 查询语言的特点

    1. 它是Neo4j图形数据库的查询语言。
    2. 它是一种声明性模式匹配语言
    3. 它遵循SQL语法。
    4. 它的语法是非常简单且人性化、可读的格式。

    4.2 问答机器人

    基于知识图谱可以构建问答机器人,这个大家可以去网上搜一下基于知识图谱的问答机器人这样的关键词,找一些相关项目练练手,从而快速入门。目前比较流行基于Python+Neo4j+Flask框架构建一个基于知识图谱的问答机器人系统。目前我也正在构建一个完整的问答机器人,由于涉及公司内部数据暂不公开,以后再来分享我的构建过程。这里可以推荐一个博文:基于电影知识图谱的智能问答系统

    4.3 服务器端部署

    由于数据量太大,本地电脑基本上跑起来会比较吃力,所以建议可以尝试在服务器端部署,之后就可以基于知识图谱构建上层应用。

    展开全文
  • Redis 10亿数据量只需要100MB内存

    千次阅读 2020-09-02 18:08:09
    本文主要和大家分享一下redis... 10亿数据量需要大的存储空间? redis位操作适合哪些应用场景? 本文redis试验代码基于如下环境: 操作系统:Mac OS 64位 版本:Redis 5.0.7 64 bit 运行模式:stand...

    本文主要和大家分享一下redis的高级特性:bit位操作。

     

    力求让大家彻底学会使用redis的bit位操作并掌握其底层实现原理!主要包含以下内容:

     

    1. redis位操作命令示例

    2. 底层数据结构分析

    3. 为什么他的算法时间复杂度是O(1)?

    4. 10亿数据量需要多大的存储空间?

    5. redis位操作适合哪些应用场景?

       

    本文redis试验代码基于如下环境:

    操作系统:Mac OS 64位

    版本:Redis 5.0.7 64 bit

    运行模式:standalone mode

     

    # redis位操作

     

    reids位操作也叫位数组操作、bitmap,它提供了SETBIT、GETBIT、BITCOUNT、BITTOP四个命令用于操作二进制位数组。

     

    先来看一波基本操作示例:

     

    SETBIT

     

    语法:SETBIT key offset value

     

    即:命令 key 偏移量 0/1

     

    setbit命令用于写入位数组指定偏移量的二进制位设置值,偏移量从0开始计数,且只允许写入1或者0,如果写入非0和1的值则写入失败:

     

     

    GETBIT

     

    语法:GETBIT key offset

     

    即:命令 key 偏移量

     

    gitbit命令用于获取位数组指定偏移量上的二进制值:

     

     

    BITCOUNT

     

    语法:BITCOUNT key

     

    即:命令 key

     

    bitcount命令用于获取指定key的位数组中值为1的二进制位的数量,之前我们写入了偏移量0的值为1,偏移量10 的值为1,偏移量8的值为0:

     

     

    BITOP

     

    语法:BITOP operation destkey key [key…]

     

    即:命令 操作 结果目标key key1 key2 …

     

    bitop命令可以对多个位数组的key进行and(按位与)、or(按位或)、xor(按位异或)运算,并将运算结果设置到destkey中:

     

     

    # 底层数据结构分析

     

    SDS是redis中的一种数据结构,叫做简单动态字符串(Simple Dynamic String),并且它是一种二进制安全的,在大多数的情况下redis中的字符串都用SDS来存储。

     

    SDS的数据结构:

    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    •  
    struct sdshdr { #记录buff数组中已使用字节的数量 #也是SDS所保存字符串的长度 int len; #记录buff数组中未使用字节的数量 int free; #字节数组,字符串就存储在这个数组里 char buff\[\];}
     

    数据存储示例:

     

     

    SDS的优点:

     

    1. 时间复杂度为O(1)

    2. 杜绝缓冲区溢出

    3. 减少修改字符串长度时候所需的内存重分配次数

    4. 二进制安全的API操作

    5. 兼容部分C字符串函数

     

    redis中的位数组采用的是String字符串数据格式来存储,而字符串对象使用的正是上文说的SDS简单动态字符串数据结构。

     

     

    大家都知道的是一个字节用的是8个二进制位来存储的,也就是8个0或者1,即一个字节可以存储十进制0~127的数字,也即包含了所有的数字、英文大小写字母以及标点符号。

     

    1Byte=8bit

    1KB=1024Byte

    1MB=1024KB

    1GB=1024MB

     

    位数组在redis存储世界里,每一个字节也是8位,初始都是:

    •  
    0 0 0 0 0 0 0 0
     

    而位操作就是在对应的offset偏移量上设置0或者1,比如将第3位设置为1,即:

    •  
    •  
    •  
    0 0 0 0 1 0 0 0#对应redis操作即:setbit key 3 1
     

    在此基础上,如果要在偏移量为13的位置设置1,即:

    •  
    •  
    •  
    setbit key 13 1#对应redis中的存储为:0 0 1 0 | 0 0 0 0 | 0 0 0 0 | 1 0 0 0
     

    # 时间复杂度

     

    GETBIT命令时间复杂度O(1)

     

    STEBIT命令时间复杂度O(1)

     

    BITCOUNT命令时间复杂度O(n)

     

    BITOP命令时间复杂度O(n)、O(n2)

     

    我们来看GETBIT以及SETBIT命令的时间复杂度为什么是O(1),当我们执行一个SETBIT key 10086 1的值的时候,reids的计算方式如下:

     

    获取到要写入位数组中的哪个字节:10086÷8=1260,需要写入到位数组的下标1260的字节

     

    获取要写入到这个字节的第几位:10086 mod 8 = 6,需要写入到这个字节的下标为6即第7位上去。

     

    通过这两种计算方式大家可以清晰的看到,位操作的GETBIT和SETBIT都是常量计算,因此它的时间复杂度为O(1)。

     

    而BITCOUNT命令需要对整个位数组的所有元素进行遍历算出值为1的有多少个,当然redis对于大数据了的bit执行bitcount命令会有一整套复杂的优化的算法,但是核心思路还是这个意思,无非是减少部分遍历查询次数。比如以128位为一次遍历,那么他的遍历次数就是所有的位数除以128。

     

    BITTOP命令则是根据不同的操作有不同的执行方式。比如AND操作,则需要查看位值为1的即可。

     

    # 存储空间计算

     

    根据上面的介绍,相信大家已经知道了基于redis的位数组数据结构存储的数据占用内存大小是怎么计算的了。比如有100亿的数据,那么它需要的字节数组:

     

    1000000000÷8÷1024÷1024≈119.21MB

     

    也就是存储10亿的数据只需要119MB左右的内存空间,这对于现在动辄16G、32G集群版的redis,完全没有问题。

     

    需要注意的是,如果你的数据量不大,那就不要把起始偏移量搞的很大,这样也是占空间的,比如我们只需要存储几百条数据,但是其中的偏移量却很大,这就会造成了很大的内存空间浪费。

     

    # 应用场景

     

    实际项目开发中有很多业务都适合采用redis的bit来实现。

     

    用户签到场景

     

    每天的日期字符串作为一个key,用户Id作为offset,统计每天用户的签到情况,总的用户签到数

     

    活跃用户数统计

     

    用户日活、月活、留存率等均可以用redis位数组来存储,还是以每天的日期作为key,用户活跃了就写入offset为用户id的位值1。

     

    同理月活也是如此。

     

    用户是否在线以及总在线人数统计

     

    同样是使用一个位数组,用户的id映射偏移量,在线标识为1,下线标识为0。即可实现用户上下线查询和总在线人数的统计

     

    APP内用户的全局消息提示小红点

     

    现在大多数的APP里都有站内信的功能,当有消息的时候,则提示一个小红点,代表用户有新的消息。

    展开全文
  • 文章目录问题描述解决方案Bloom...假设你现在要给项目添加IP黑名单功能,此时你手上有大约 1亿个恶意IP的数据集,有一IP发起请求,你如何判断这IP在不在你的黑名单中? 类似这种问题Java自己的Collection和Map很



    问题描述

    在开发过程中,经常要判断一个元素是否在一个集合中。假设你现在要给项目添加IP黑名单功能,此时你手上有大约 1亿个恶意IP的数据集,有一个IP发起请求,你如何判断这个IP在不在你的黑名单中?

    类似这种问题用Java自己的Collection和Map很难处理,因为它们存储元素本身,会造成内存不足,而我们只关心元素存不存,对于元素的值我们并不关心,具体值是什么并不重要。

    解决方案

    BloomFilter(布隆过滤器)

    布隆过滤器可以用来判断某个元素是否在集合内,具有运行快速,内存占用小的特点,它是一个保存了很长的二级制向量,同时结合 Hash 函数实现的。而高效插入和查询的代价就是,它是一个基于概率的数据结构,只能告诉我们一个元素绝对不在集合内,对于存在集合内有一定的误判率

    fpp

    因为布隆过滤器中总是会存在误判率,因为哈希碰撞是不可能百分百避免的。布隆过滤器对这种误判率称之为假阳性概率,即:False Positive Probability,简称为 fpp。

    在实践中使用布隆过滤器时可以自己定义一个 fpp,然后就可以根据布隆过滤器的理论计算出需要多少个哈希函数和多大的位数组空间。需要注意的是这个 fpp 不能定义为 100%,因为无法百分保证不发生哈希碰撞。

    下图表示向布隆过滤器中添加元素 https://blog.csdn.net/booksseahttps://www.abc.com 的过程,它使用了 func1 和 func2 两个简单的哈希函数。

    对写入的数据做 H 次 hash 运算定位到数组中的位置,同时将数据改为 1 。当有数据查询时也是同样的方式定位到数组中。 一旦其中的有一位为 0 则认为数据肯定不存在于集合,否则数据可能存在于集合中。

    通过其原理可以知道,可我们可以提高数组长度以及 hash 计算次数来降低误报率,但是相应的 CPU、内存的消耗也会相应的提高;这需要我们根据自己的业务需要去权衡选择。

    布隆过滤器的特点

    布隆过滤有以下2个特点:

    • 只要返回数据不存在,则肯定不存在。
    • 返回数据存在,但只能是大概率存在。

    在有限的数组长度中存放大量的数据,即便是再完美的 Hash 算法也会有冲突,所以有可能两个完全不同的 A、B 两个数据最后定位到的位置是一模一样的。这时拿 B 进行查询时那自然就是误报了。

    布隆过滤器中的数据可不可以删除

    布隆过滤器判断一个元素存在就是判断对应位置是否为 1 来确定的,但是如果要删除掉一个元素是不能直接把 1 改成 0 的,因为这个位置可能存在其他元素,所以如果要支持删除,最简单的做法就是加一个计数器,就是说位数组的每个位如果不存在就是 0,存在几个元素就存具体的数字,而不仅仅只是存 1,那么这就有一个问题,本来存 1 就是一位就可以满足了,但是如果要存具体的数字比如说 2,那就需要 2 位了,所以带有计数器的布隆过滤器会占用更大的空间。

    <dependency>
        <groupId>com.baqend</groupId>
        <artifactId>bloom-filter</artifactId>
        <version>1.0.7</version>
    </dependency>
    

    新建一个带有计数器的布隆过滤器 CountingBloomFilter:

    package com.lonelyWolf.redis.bloom;
    
    import orestes.bloomfilter.FilterBuilder;
    
    public class CountingBloomFilter {
        public static void main(String[] args) {
            orestes.bloomfilter.CountingBloomFilter<String> cbf = new FilterBuilder(10000,
                    0.01).countingBits(8).buildCountingBloomFilter();
    
            cbf.add("zhangsan");
            cbf.add("lisi");
            cbf.add("wangwu");
            System.out.println("是否存在王五:" + cbf.contains("wangwu")); //true
            cbf.remove("wangwu");
            System.out.println("是否存在王五:" + cbf.contains("wangwu")); //false
        }
    }
    

    构建布隆过滤器前面 2 个参数一个就是期望的元素数,一个就是 fpp 值,后面的 countingBits 参数就是计数器占用的大小,这里传了一个 8 位,即最多允许 255 次重复,如果不传的话这里默认是 16 位大小,即允许 65535次重复。

    建议使用Guava自带的布隆过滤器,直接传入预期的数据量以及fpp,它会自动帮我们计算数组长度和哈希次数

    布隆过滤器应该设计为多大?

    假设在布隆过滤器里面有 k 个哈希函数,m 个比特位(也就是位数组长度),以及 n 个已插入元素,错误率会近似于 (1-ekn/m)k,所以你只需要先确定可能插入的数据集的容量大小 n,然后再调整 k 和 m 来为你的应用配置过滤器。

    布隆过滤器应该使用多少个哈希函数?

    对于给定的 m(比特位个数)和 n(集合元素个数),最优的 k(哈希函数个数)值为: (m/n)ln(2)

    布隆过滤器的时间复杂度和空间复杂度?

    对于一个 m(比特位个数)和 k(哈希函数个数)值确定的布隆过滤器,添加和判断操作的时间复杂度都是 O(k),这意味着每次你想要插入一个元素或者查询一个元素是否在集合中,只需要使用 k 个哈希函数对该元素求值,然后将对应的比特位标记或者检查对应的比特位即可。

    Guava的布隆过滤器的实现

    Guava有自带的布隆过滤器的实现

    public class BloomFilterTest {
    
        public static void main(String[] args) {
            long star = System.currentTimeMillis();
            BloomFilter<Integer> filter = BloomFilter.create(
                    Funnels.integerFunnel(),
                    //预计存放多少数据
                    10000000,
                    //可以接受的误报率
                    0.01);
    
            for (int i = 0; i < 10000000; i++) {
                filter.put(i);
            }
    
            Assert.isTrue(filter.mightContain(1),"不存在");
            Assert.isTrue(filter.mightContain(2),"不存在");
            Assert.isTrue(filter.mightContain(3),"不存在");
            Assert.isTrue(filter.mightContain(10000000),"不存在");
            long end = System.currentTimeMillis();
            System.out.println("执行时间:" + (end - star));
    
        }
    }
    

    BitMap

    BitMap不会存在误判的情况,位图也是布隆过滤器的实现,但是占用内存空间随集合内最大元素的增大而增大。而布隆过滤器,因为其可能一个bit为多个元素作标识,这就保证了它的空间利用率。这2种方式根据业务进行选择。

    以32位整型为例,它可以表示数字的个数为2^32. 可以申请一个位图,让每个整数对应的位图中的一个bit,这样2^32个数需要的位图的大小为512MB。具体实现的思路为:申请一个512MB的位图,并把所有的位都初始化为0;接着遍历所有的整数,对遍历到的数字,把相应的位置上的bit设置为1.最后判断待查找的数对应的位图上的值是多少,如果是0,那么表示这个数字不存在,如果是1,那么表示这个数字存在。

    Java中有BitMap的实现类,BitSet

    public class BitMapTest {
            public static void main(String[] args) {
                    int[] array = {3, 8, 5, 7, 1};
                    BitSet bitSet = new BitSet(5);
     
                    for (int i = 0; i < array.length; i++) {
                            bitSet.set(array, true);
                    }
     
                    bitSet.stream().forEach(e -> System.out.println(e));
     
            }
    }
    

    Redis里也有BitMap的实现。这个下回出篇文章讲。

    展开全文
  • 公司对合作商家提供一付费级产品,这商业产品背后涉及到数百人的研发团队协作开发,包括各种业务系统来提供很强大的业务功能,同时在整个平台中包含了一至关重要的核心数据产品,这个数据产品的定位是全方位...
  • 组合查询为条件组合查询,在很场景下都有使用。购物网站中通过勾选类别、价格、销售量范围等属性来对所有的商品进行筛选,筛选出满足客户需要的商品,这是一种典型的组合查询。在小数据量的情况下,后台通过简单...
  • 使用Python Pandas处理亿数据

    千次阅读 2017-08-12 15:52:18
    数据分析领域,最热门的莫过于Python和R语言,此前有一篇文章《别老扯什么Hadoop了,你的数据...这次拿到近亿条日志数据,千万级数据已经是关系型数据库的查询分析瓶颈,之前使用过Hadoop对大量文本进行分类
  • mysql尝试一下1.7亿数据

    千次阅读 2018-11-24 13:20:03
    是我在大三下学期做过的一次实训课程。 选题的数据来源是,同济大学2011数学建模夏令营试题的数据。 实验报告的位置:https://download.csdn.net/download/qq_35640964/10804674 整个操作大概是消耗了一...
  • 任何关于算法、编程、AI行业知识或博客内容的问题,可以随时扫码关注公众号「图灵的猫」,加入”学习小组“,沙雕博主在线答疑~此外,公众号内还有更AI、算法、编程和大数据知识分享,以及免费的SSR节点和学习资料...
  • 作者:小小明 10年编码经验,熟悉...某MOOC课程网站的老师需要统计每学生成绩最相近的10学生,距离计算公式是每门课程的成绩之差的绝对值求和。 例如,学生1的成绩为(83,84,86,99,87),学生2的成绩为(83,84,86,.
  • 获取一亿数据获取前100最大值

    万次阅读 2014-09-25 18:40:26
    获取一亿数据获取前100最大值
  • 如何从10亿数据中快速判断是否存在某一元素

    千次阅读 多人点赞 2021-02-26 11:02:49
    如何从10亿数据中快速判断是否存在某一元素 前言 缓存雪崩 解决方案 缓存击穿 解决方案 缓存穿透 解决方案 布隆过滤器(Bloom Filter) 什么是布隆过滤器 位图(Bitmap) 哈希碰撞 布隆过滤器的 2 大特点 fpp 布隆...
  • 3月24日晚,锘崴科技创始人、董事王爽先生做客万向区块链蜂巢研习社直播间,分享隐私计算行业概述、隐私计算赋能数据要素化、隐私计算赋能医疗领域的应用等当下热门议题。 下文根据速记整理,略有不影响原意的...
  • 总第391篇2020年 第14篇美团自研的 OCTO 数据中心(简称 Watt)日均处理万亿数据量,该系统具备较好的扩展能力及实时性,千台实例集群周运维成本低于10分钟。本文将详细阐述...
  • 如何实现上亿数据的精准计数?

    千次阅读 2021-01-28 14:29:04
    数据量达到亿级别时,计数任务的执行效率已经低到令人不忍直视。在闲鱼团队的关系系统中,我们采用了这样一种方式来实现亿级别数据的毫秒级计数。挑战闲鱼现有的业务场景中,用户收藏宝贝、关注他人的数据量,已经...
  • 前两天面试3面学长问我的这问题(想说TEG的3面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这问题还是建立最小堆比较好一些。 先拿10000数建堆,然后一次...
  • 近年来,随着大数据分析技术的普及和物联网产业的兴起,越来越的企业开始重视海量数据的收集和分析处理活动,希望从庞大的数据资料中挖掘出高价值的信息和洞见。而在数据规模快速膨胀的同时,企业对...
  • 本文根据dbaplus社群第199期线上分享整理而成,文末还有直播回放~王海胜趣头条数据中心大数据开发工程师8年互联网工作经验,曾在eBay、唯品会、趣头条等公司从事大数据开发相关工作,...
  • **数据正在重新塑造人类生活的方方面面,IDC Research统计2019年大数据和分析市场的销售收入约为1870亿美元。跨机构、跨行业的数据融合、联合分析和建模的需求日趋增加。但由于数据本身可复制,易传播,一经分享无法...
  • 1,设计原则 正确性,可读性,健壮性, 高效性与低内存 内存占用小,CPU占用最小,运算最快 ...一数和1亿个数不一样。 导致结果不准确。 所以需要自己计算时间复杂度 时间复杂度表达方式:O(n) O(ologn) ...
  • 计算机如何区分指令和数据(一)

    万次阅读 多人点赞 2019-09-03 09:44:27
    要了解指令和数据是什么?在计算机中有什么作用?以及它们怎样存储?才能回答如何区分它们以及为何要区分。首先我们要搬出冯诺依曼计算机体系架构,因为它回答了...3.指令和数据二进制表示。 4.指令由操作码和...
  • Jindo 是阿里云基于 Apache Spark / Apache Hadoop 在云上定制的分布式计算和存储引擎。 Jindo 原是阿里云 开源大数据团队的内部研发代号, 取自筋斗(云)的谐音,Jindo 在开源基础上做了大量优化和扩展, 深度集成和...
  • 现在有一非常庞大的数据,假设全是 int 类型。现在我给你一数,你需要告诉我它是否存在其中(尽量高效)。 需求其实很清晰,只是要判断一个数据是否存在即可。但这里有一比较重要的前提:非常庞大的数据。   ...
  • Apache Flink 在快手万亿数据的应用实践总结

    万次阅读 多人点赞 2019-07-17 15:07:35
    作者:董亭亭 整理:蒋晓峰 作者介绍:董亭亭,快手大数据架构实时计算引擎团队负责人。...本次的分享包括以下三部分: 介绍 Flink 在快手的应用场景以及目前规模; 介绍 Flink 在落地过程的技术演进过程...
  • 计算数据结构篇 - 哈希算法 (Hash)

    万次阅读 多人点赞 2020-01-21 14:02:00
    计算数据结构篇 - 哈希算法 (Hash) 哈希算法的定义和原理非常简单,基本上一句话就可以概括了。将任意长度的二进制值串映射为固定长度的二进制值串,这映射的规则就是哈希算法,而通过原始数据映射之后得到的二...
  • 对于Mysql大量数据查询速度慢的问题

    千次阅读 2021-01-21 12:24:53
    1.如果mysql数据量过大,当查询的时候耗时比较,则会影响页面数据展示。给客户的直观反应的:点击了某个查询功能,结果等了差不多十几秒才反应出来,这样的体验感太差了。2.为了增加反应速度。一般来是建立索引,...
  • 1T数据到底有大?

    千次阅读 2018-04-18 18:09:04
    一英里不是个很的距离,一立方英里相对于地球也不会让人觉得是个很大的空间。然后我说,这个空间内能装下全世界所有人,你会不会觉到很惊讶?不过这话不是我说的,是美国作家房龙在一本书里写...似乎T不是个多大的...
  • 数据倾斜是大数据领域绕不开的拦路虎,当你所需处理的数据量到达了上亿甚至是千亿条的时候,数据倾斜将是横在你面前一道巨大的坎。 迈的过去,将会海阔天空!迈不过去,就要做好准备:很可能有几周甚至几月都要...
  • 这篇文章中的干货蛮的, node 写 BFF 或者后端的小伙伴可以对比一下自己项目,学习下。 以下文章来源于较真的前端,作者英俊潇洒你冲哥 较真的前端 前端开发者交流与呵护平台 本文首发于知乎,大家可以...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 116,618
精华内容 46,647
关键字:

计算1亿个数据用多长时间