最新 | 最热门 | 最高评价

+0  100行代码的压缩前缀树: 50% smaller

Tag: algo | memory | succinct | trie | bitmap
张炎泼(xp) 发于 2021年02月01日 08:00 | 点击: 84 | 展开摘要
这文介绍一个压缩前缀树实现的sorted set(github: succinct.Set), 区区95行代码, 包含了一组完整的功能:

用 前缀树 存储一个排序数组, 去掉指针, 压缩掉50%的空间;
例如在本文的例子中, 存储2.4MB的200万个单词, 只需要1.2MB.

创建: 从key列表创建一个压缩的前缀树;

查询: 支持Has() 操作来查询1个key是否存在;

优化: 通过索引来加速 bitmap 的操作, 将较大的 bitmap 操作优化到O(1)的

查看全文: http://www.udpwork.com/item/17474.html

+0  slimarray: gzip的压缩率, 即时访问

Tag: algo | array | 数组 | compress | succinct
张炎泼(xp) 发于 2020年11月15日 08:00 | 点击: 83 | 展开摘要
slimarray

场景和问题

在时序数据库, 或列存储为基础的系统中, 很常见的形式就是存储一个整数数组,
例如 slim 这个项目按天统计的 star 数:

这类数据有有很明显的统一的变化趋势, 对这类数据的存储,
我们可以利用数据分布的特点, 将整体数据的大小压缩到几分之一.
这就是 slimarray 要做的事情.

使用 slimarray, 可以将数据容量减小到gzip差不多的大小,
同时还能允许直接访问这些数据!
测试中我们选择了2组随机数, 以及现实中的

查看全文: http://www.udpwork.com/item/17477.html

+0  200行代码实现基于paxos的kv存储

Tag: algo | distributed | replication | paxos | kv | 分布式 | 存储
张炎泼(xp) 发于 2020年10月28日 08:00 | 点击: 85 | 展开摘要
前言

写完 paxos的直观解释 之后,
网友都说疗效甚好, 但是也会对这篇教程中一些环节提出疑问(有疑问说明真的看懂了

查看全文: http://www.udpwork.com/item/17478.html

+0  后分布式时代: 多数派读写的’少数派’实现

Tag: algo | distributed | quorum | majority | replication | paxos | raft | 分布式 | 多数派
张炎泼(xp) 发于 2020年10月18日 08:00 | 点击: 91 | 展开摘要
前言

paxos可以看做是2次 多数派读写 完成一次强一致读写. 多数派要求半数以上的参与者(paxos中的Acceptor)接受某笔操作. 但 多数派读写 并不一定需要多于半数的参与者, 分布式系统中某些场合的优化, 可以通过减少参与者数量来完成的.

多数派读写:分布式系统的基础

分布式系统中, 其中一个基础的问题是如何在不可靠硬件(低可用性)基础上构建可靠(高可用性)的服务,
要达成这个目标, 核心的手段就是复制(例如一份数据存3个副本).
而复制过程中的一致性

查看全文: http://www.udpwork.com/item/17479.html

+0  可靠分布式系统-paxos的直观解释

Tag: algo | distributed | consensus | fault-tolerant | quorum | replication | paxos | 分布式 | 一致性 | 容错 | 多数派
张炎泼(xp) 发于 2020年06月01日 08:00 | 点击: 83 | 展开摘要
前言

paxos是什么?

在分布式系统中保证多副本数据强一致的算法.

paxos有啥用?

没有paxos的一堆机器, 叫做分布式;

有paxos协同的一堆机器, 叫分布式系统.

Google Chubby的作者Mike Burrows说过:

这个世界上只有一种一致性算法,那就是Paxos …

其他一致性算法, 都可以看做paxos在实现中的变体和扩展.

另外一个经常被提及的分布式算法是raft, raft的贡献在于把一致性算法落地.
因为 Leslie

查看全文: http://www.udpwork.com/item/17480.html

+0  Prolog 语言入门教程

Tag: Algorithm
阮一峰 发于 2019年01月28日 09:17 | 点击: 1531 | 展开摘要
Prolog 是一种与众不同的语言,不用来开发软件,专门解决逻辑问题。比如,"苏格拉底是人,人都会死,所以苏格拉底会死"这一类的问题。

Prolog 就是"逻辑编程"(programming of Logic)的意思。只要给出事实和规则,它会自动分析其中的逻辑关系,然后允许用户通过查询,完成复杂的逻辑运算。

本文简单介绍如何使用 Prolog 语言,主要参考了 xmonader 的教程。

一、SWI-Prolog

学习之前,请安装 Prolog 的运行环境 SWI-P

查看全文: http://www.udpwork.com/item/17363.html

+0  哈希碰撞与生日攻击

Tag: Algorithm
阮一峰 发于 2018年09月05日 20:41 | 点击: 1524 | 展开摘要
一、哈希碰撞是什么?

所谓哈希(hash),就是将不同的输入映射成独一无二的、固定长度的值(又称"哈希值")。它是最常见的软件运算之一。

如果不同的输入得到了同一个哈希值,就发生了"哈希碰撞"(collision)。

举例来说,很多网络服务会使用哈希函数,产生一个 token,标识用户的身份和权限。

AFGG2piXh0ht6dmXUxqv4nA1PU120r0yMAQhuc13i8

上面这个字符串就是一个哈希值。如果两个不同的用户,得到了同样的 token,就发生

查看全文: http://www.udpwork.com/item/17077.html

+0  彩票的数学知识

Tag: Algorithm
阮一峰 发于 2018年04月07日 23:22 | 点击: 1370 | 展开摘要
彩票怎样才能中奖?

理论上,只能靠运气。但是,如果规则设计得不好,就可以钻漏洞。

2005年2月,美国的一个彩票品种,就出现了漏洞,被麻省理工学院的学生发现了。随后的七年,这个学生反复购买这个品种,一共赚到了300万美元。

本文介绍他怎么做的,以及其中的数学原理。我依据的材料,主要来自数学教授 Jordan Ellenberg 在斯坦福大学的一次演讲(Youtube)。

一、期望值

彩票最重要的数学概念,叫做"期望值"(expected value),即同一种行为多

查看全文: http://www.udpwork.com/item/16773.html

+0  图像与滤波

Tag: Algorithm
阮一峰 发于 2017年12月13日 08:16 | 点击: 1605 | 展开摘要
我对图像处理一直很感兴趣,曾经写过好几篇博客(1,2,3,4)。

前几天读到一篇文章,它提到图像其实是一种波,可以用波的算法处理图像。我顿时有一种醍醐灌顶的感觉,从没想到这两个领域是相关的,图像还可以这样玩!下面我就来详细介绍这篇文章。

一、为什么图像是波?

我们知道,图像由像素组成。下图是一张 400 x 400 的图片,一共包含了 16 万个像素点。

每个像素的颜色,可以用红、绿、蓝、透明度四个值描述,大小范围都是0 ~ 255,比如黑色是[0, 0, 0, 25

查看全文: http://www.udpwork.com/item/16538.html

+0  LeetCode付费题目(一)

Tag: Algorithm & Data Structure | LeetCode
四火 发于 2017年11月07日 03:30 | 点击: 3120 | 展开摘要
LeetCode 300题以内需要付费才能查看的所有题目解答。

156

Binary Tree Upside Down

157

Read N Characters Given Read4

158

Read N Characters Given Read4 II – Call multiple times

159

Longest Substring with At Most Two Distinct Characters

161

One Edit

查看全文: http://www.udpwork.com/item/16493.html

+0  正态分布为什么常见?

Tag: Algorithm
阮一峰 发于 2017年08月02日 07:33 | 点击: 2260 | 展开摘要
统计学里面,正态分布(normal distribution)最常见。男女身高、寿命、血压、考试成绩、测量误差等等,都属于正态分布。

以前,我认为中间状态是事物的常态,过高和过低都属于少数,这导致了正态分布的普遍性。最近,读到了 John D. Cook 的文章,才知道我的这种想法是错的。

正态分布为什么常见?真正原因是中心极限定理(central limit theorem)。

"多个独立统计量的和的平均值,符合正态分布。"

上图中,随着统计量个数的增加,它们和的平

查看全文: http://www.udpwork.com/item/16373.html

+0  求第K个数的问题

Tag: Algorithm & Data Structure | Recommended | PriorityQueue | | 快排
四火 发于 2017年07月14日 13:01 | 点击: 1641 | 展开摘要
一道经典的题目。给一堆乱序的数,如果它们从小到大排好,求第k个是多少。假设排列的下标从1开始,而非0开始。

这个问题如此之简单而熟悉,可它却可以是很多现实问题的某一个子问题的抽象。它本身相关的问题其实就不少,而且还可以不断演进,成为不同复杂程度的问题。

看到这个问题,脑海里的第一反应是一左一右红蓝两条分支——堆排序或者快排。Java中快排用Arrays.sort就可以了,如果是堆排序需要用到PriorityQueue。 用Arrays.sort写起来最简单(这里的参数校验

查看全文: http://www.udpwork.com/item/16349.html
|<<<1234567>>>| 一共9页, 98条记录