w******1
发帖数: 520 | 1 什么是BITMAP, 怎么个结构啊？
看到很多人在讨论BITMAP， 可是GOOGLE BITMAP， 出来的结果都不是算法啊， 都是图
像处理的。
用128MB的内存做一个BitMap~
然后把原来的文件遍历一次,每读一个数都在上述BitMap中标记~按位取或预算~
索引就是这个数字的大小~结束后,扫描bitMap,找到没有标记的即可~
for(unsigned int i=0;i<0xffffffff;i++){ unsigned temp=next integer from
inputfile; bitmap[temp]=1;}for(unsigned int i=0;i<0xffffffff;i++){
if(bitmap[i]==0) output(i);} 4个月前 by rex.nani
关于代码格式化：把代码的那一部分部分全选，然后点击101010按钮 －
又：4Billion的内容，128M是不够的 －
@半瓶墨水: 128MByte*8=1Gbits=2^32 按位存的话是可以的吧~ －
@rex |
|
w******1
发帖数: 520 | 2 7) Explain about the role of bitmap indexes to solve aggregation problems?
Bitmaps are very useful in start schema to join large databases to small
databases. Answer queries and bit arrays are used to perform logical
operations on the databases. Bit map indexes are very efficient in handling
Gender differentiation; also repetitive tasks are performed with much larger
efficiency.
8) Explain about Encoding technique used in bitmaps indexes?
Bitmaps commonly use one bitmap for every single distinct |
|
w******1
发帖数: 520 | 3 OLAP - role of bitmap indexes to solve aggregation problems - March 08, 2009
at 22:00 PM by Rajmeet Ghai
Explain the role of bitmap indexes to solve aggregation problems.
Bitmap indexes are useful in connecting smaller databases to larger
databases. Bit map indexes can be very useful in performing repetitive
indexes. Multiple Bitmap indexes can be used to compute conditions on a
single table.
OLAP - role of bitmap indexes to solve aggregation problems - Jan 10, 2010
at 18:50 PM by Vidya Sagar
E |
|
w****o
发帖数: 2260 | 4 通常说的bitmap是不是指的就是一串1/0的bits?
C++ STL里的bitset是不是就是一种实现bitmap的方式？
不过发现bitset定义的时候要申明大小，比如 bitset<50>就是大小为50bits的bitmap,
如果程序运行中想增加size该怎么办呢？
谢谢！ |
|
s**********o
发帖数: 14359 | 5 BJ，那个COLUMNSTORE INDEX是不是ORACLE BITMAP INDEX啊，记得以前就说INDEX在
GENDER上的时候，用BITMAP INDEX比较好。 |
|
c*********t
发帖数: 2921 | 6 经常看到面试的问题可以用bitmap来解决？
谁能说说Bitmap 是什么东西？是个特殊的数据结构吗？如何用？什么时候用？是STL的
一部分吗？
哪有这方面的资料？ |
|
|
f****6
发帖数: 4472 | 8 对方ID:
bitmap
Feedback (+/-/0):
+
具体交易内容:
Amex points
我的评价:
转点很快
交易原始贴链接: |
|
|
|
f******3
发帖数: 63 | 11 对方ID:
bitmap
Feedback (+/-/0):
+
具体交易内容:
UA miles
我的评价:
付款迅速，信誉优秀。 |
|
|
a*u
发帖数: 97 | 13 问题：实现一个10000000长的bitmap。
programming pearls里面第一个例子的相关联系题要用到的，做练习的时候才发现不清
楚这个java里面怎么实现 - 我不怎么用c的。。。
谢谢大家先。 |
|
a*********9
发帖数: 523 | 14 你说的是BITSET吧，可以查查C++的相关资料。
BITMAP在图象里是另一个概念了。
from
|
|
w******1
发帖数: 520 | 15 谢谢楼上。我看答案是 bitmap
不是BITSET, BITSET 是位的操作吧 |
|
|
s**y
发帖数: 151 | 17 他们讨论的是Bit-Map，不是Bitmap. |
|
|
f*******l
发帖数: 66 | 19 use a larger bitset?
or think of other structure to store more bitset
say vector > bitsetArray
bitmap, |
|
w****o
发帖数: 2260 | 20 就是说bitset可以当成bitmap用，对吧？！ |
|
B*****g
发帖数: 34098 | 21 我觉得像，想着有空深挖一下bitmap工作原理 |
|
s*i
发帖数: 5025 | 22 3 lines in C#:
Bitmap bmp =....
Graphics g = bmp.FromImage...
g.DrawString...
You should be able to do it in managed c++ same way |
|
S*******t
发帖数: 97 | 23 看了programming pearls里面的bitmap sorting,
大致上的idea是明白了，但是看了书后面的源码，
实在不明白那三个function set, clr test实现
的原理。有没有人可以解释一下？
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];
void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); } |
|
d*****r
发帖数: 39446 | 24 【此篇文章是由自动发信系统所张贴】
bitmap 申请加入本俱乐部的请求已经通过审批, 成为本俱乐部的正式成员, 特此通知. |
|
f**d
发帖数: 768 | 25 这是一本计算神经科学的优秀著作，全文拷贝这里（图和公式缺），有兴趣的同学可以
阅读
如需要，我可以分享PDF文件（－－仅供个人学习，无商业用途）
From Computer to Brain
William W. Lytton
From Computer to Brain
Foundations of Computational Neuroscience
Springer
William W. Lytton, M.D.
Associate Professor, State University of New York, Downstato, Brooklyn, NY
Visiting Associate Professor, University of Wisconsin, Madison
Visiting Associate Professor, Polytechnic University, Brooklyn, NY
Staff Neurologist., Kings County Hospital, Brooklyn, NY
In From Computer to Brain: ... 阅读全帖 |
|
y****n
发帖数: 743 | 26 1. 因为对称，计算1/8圆，就可以画整个圆。
2. 设d=x^2+y^2-r^2，当d>0，说明点在圆外
3. 最开始x=r,y=0
4. 下一个点，y++：
因为公式：(y+1)^2=y^2+2y+1，所以d+=2y+1。
如果d>0，则x--，同时d-=2x-1；
5. 重复第四步，直到1/8圆
public void DrawCircle(Bitmap bitmap, int centerX, int centerY, int r)
{
int x = r;
int y = 0;
int diff = 0;
while (x >= y)
{
DrawPixel(bitmap, centerX + x, centerY + y);
DrawPixel(bitmap, centerX - x, centerY + y);
DrawPixel(bitmap, centerX + x, centerY - y);
DrawPixel(bitmap, centerX - x, centerY - y);
DrawPixel(bitmap, centerX + y, centerY + x... 阅读全帖 |
|
c*****d
发帖数: 6045 | 27 3.
举个例子，当学习bitmap index的时候，
a. 什么是bitmap index
b. 为什么要用bitmap index
c. bitmap index和b-tree index在应用上有什么区别？谁适合oltp,谁适合dss？
d. 为什么有这样的区别，bitmap index和b-tree index在结构上有什么区别？
e. b-tree index存储null值吗？bitmap呢？
f. 怎么证明b-tree or bitmap index是否存储null值？ |
|
c*****d
发帖数: 6045 | 28 3.
举个例子，当学习bitmap index的时候，
a. 什么是bitmap index
b. 为什么要用bitmap index
c. bitmap index和b-tree index在应用上有什么区别？谁适合oltp,谁适合dss？
d. 为什么有这样的区别，bitmap index和b-tree index在结构上有什么区别？
e. b-tree index存储null值吗？bitmap呢？
f. 怎么证明b-tree or bitmap index是否存储null值？ |
|
d**********o
发帖数: 1321 | 29 一个单词引发的血案（2）
如果说，因为12、12这个周五upload到github上去的review docs上一个词特别刺眼，
那一定是批在review第二页纸下方的这个“practice”了。
记得那个周五中午，我见代课老师的办公室门是开着的，便敲门应允进去了。老师说他
正在改我的review。说到最后，他指给我看我review的最后几段的“practise”说，他
知道英国等一些国家名字也用“practise”，但在美国，作动词用时是practise, 但作
名词用的时候还是用“practice”，并把这名词规规矩矩、端端正正地写在了这页纸的
下方。我不以为意。
及至这天下午紧接着系里发出的邮件，我也以为天上掉馅饼，系里有多的奖学金的话，
不是说我春天也可以拿到TA了吗？LinkedIn上当天也刮这种风，虽然自己当时并不没有
回，但晚上临睡前还是发信回复给系里，问一下到底是什么情况。但系里小秘第二天中
午用她的周末时间给我的回复是，那是发给全系的邮件，即使系里有奖学金，我是没有
资格的，因为先前导师与我已经讲好了春天我只能注册一个学分。我友好地回复系里小
秘的邮件。不给奖学金不是... 阅读全帖 |
|
z****e
发帖数: 54598 | 30 居然官方api里面没有找到
嗯，自己按照stackoverflow上的写了几个
其中一个是horizontal flip
还有一个是用最小内存消耗的方式读取图片到内存
default的8888格式吃内存太离谱了
还有就是android居然限制一个app只能16m
我插，让我想起小时候玩sfc，老板拿个磁盘一点一点读
也就只有16m
private static Map rectCache;
static {
rectCache = new HashMap();
}
public static void drawImage(Canvas canvas, Bitmap bitmap, Rect source,
Rect dest, Paint paint, boolean horizontalRotate) {
if (horizontalRotate) {
if (rectCache.get(dest) == null) {
re... 阅读全帖 |
|
n*****t
发帖数: 22014 | 31 来自主题: Programming版 - 简单就是美 另外，补充一下我的算法，跟大家探讨：
#define T0102 1
#define T0103 2
....
#define T0120 190
初始化的时候，将每张票按 from to enqueue，queue 中是否有票，建 bitmap。
queue[T0102], queue[T0103] .... queue[T0120]
给定 from to，需要查询的队列优先级是固定的：
queue_to_check[T0305] = { T0305, T0306, T0205 ...T0120}
bitmap[T0305] = { 0, 0, 1}
需要查询的时候:
1、检查 bitmap，最多 190 个 bit
for (i=0; i<3; i++)
if (bitmap[i] != 0) found();
2、bitmap[i] 中找到最高位为 1 的，然后比较 32 bit，16， 8 bit
， 3 次比较，都在寄存器里，最后是 7 次循环找到那个 bit
所以最坏情况：3 memory read, 10 reg comp
缺陷：一个 queue 的有票/... 阅读全帖 |
|
j********e
发帖数: 1192 | 32 我没有说字符集相同就能scramble，字符集相同是必要条件，而不充分。
我的做法是，先找到一个位置i在s1,j在s2使得分割后的4个字符串两两
有相同的字符集（i=j 或者i=N-j)。然后接着对这2对字符串继续做同样
的事情连寻找分割位置。这样递归下去，如果有某对字符串无法找到分割
位置，则表示失败。否则，最后分隔最小的字符串只有一个字符。就可以
判断scramble成功。
问题是，如果有多个分割位置，是否任选一个都可以？如果必须测试每个可能的分割位置，那复杂度就不好说了。
下面是我的简单实现代码，通过了leetcode的online judge (包括judge large)。这段代码中会处理所有可能的分割位置。如果只选第一个可能的分割位置，有一个测试失败了。
#include
#include
#include
#include
using namespace std;
#define BITMAP_LEN 256
bool compare_char_set(const char *s1, con... 阅读全帖 |
|
c********t
发帖数: 5706 | 33 是不是我改java改的有问题
bitmap判断那句改成下面的是不是对的？
if (((1 << i) & bitmap) != 0) {
continue;
}
static void rearrange(ArrayList list) {
int bitmap = 0; // "O(1)" space for length < (1 << 32)
int k = list.size() / 2;
int n = list.size();
for (int i = 0; get_index(i) < k; ++i) {
int cur = get_index(i);
if (((1 << i) & bitmap) != 0) {
continue;
}
int next = cur * 2;
String tmp = list.get(cur);
while (true) {
if... 阅读全帖 |
|
Y********f
发帖数: 410 | 34 怎么知道有没有超时呢？
贴一下俺的，抛砖引玉
int processOneCase(int n, int k, int a, int b, int c, int r)
{
// first k element,
// if a element < k, but it appear in later position,
//put all these emement but last element INT_MAX
vector vect(k, INT_MAX);
// whether a [0,k) show in the above vector
vector bitMap(k+1, 0);
// used for duplicate element for vect
map posMap;
for (int i = 0; i < k; i++)
{
int value = (i == 0) ? a : (b * (long long)vect[... 阅读全帖 |
|
y****n
发帖数: 743 | 35 DrawPixel没有玄机
public void DrawPixel(Bitmap bitmap, int x, int y)
{
if ((x >= 0) && (x < bitmap.Width) &&
(y >= 0) && (y <= bitmap.Height))
bitmap.SetPixel(x, y, Color.Blue);
} |
|
G*****h
发帖数: 33134 | 36 haha 加了个
/etc/fonts/conf.d/64-wqy-bitmap-song.conf
monospace 族里加了温泉医中文点阵字体
立马就生效了
现在中文终于爽了
英文还是该死的 AA 糊糊字体
怎么办呢？
serif
WenQuanYi Bitmap Song
sans-serif
... 阅读全帖 |
|
b********e
发帖数: 693 | 37 You have millions of documents numbered 1,2,3,4,5 ......
You also have a mapping from a word to the list of documents that contains i
t
Find all the 'pair of words' that occur together in one and only document
Bitmap
It can be done in O(m+n)/O(Max(m,n)) time complexity and O(m*n bits).
We can calculate a BitMap for the given work by setting all the bits corresp
onding to each file(number). This BitMap will take O(m) space. The BitMap of
both words can be compared in o(1) time (any weird insane c |
|
a******7
发帖数: 106 | 38 cool man! Thanks! I think you can definitely get an offer.
About the data structure for tetris game, my idea is to use a bitmap to
express each shape, and store 4 rotated shaped in circular double link
list, each time when rotate function is called, it either point to the
left and right elem, which is pre-computed bitmap.
The board is also a bitmap, say M*M, so as long as we have the position
of the shape on board, say the rightmost coordinates (x,y), and the size
of the shape bitmap N*N. For ea... 阅读全帖 |
|
g**********y
发帖数: 14569 | 39 基本想法：把Element映射到数字，然后用Bitmap来计算包容关系。
pesudo-code =>
foreach set in sets {
Bitmap b1 = transform(set);
boolean add = true;
foreach b2 in map.keySet() {
Bitmap b3 = b1.and(b2);
if (b3.equals(b2)) {
bitmaps.remove(b2);
}
else if (b3.equals(b1)) {
add = false;
}
}
if (add) map.put(b1, set);
}
return map.values(); |
|
h*****n
发帖数: 93 | 40 my two cents:
1.先做个bit map.O(N) time. bitmap中放数在array中的位置.
bitmap(i) = position of i in Array.
2. bitmap中连续的数,按array中的位置,那bitmap的value排序. 最坏O(NlogN)
2b. 对排序的数找最长连续数列 (需要考虑重复数字). O(N)
好像重复的数字也可以. |
|
r******r
发帖数: 700 | 41 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
r******r
发帖数: 700 | 42 海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把
整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash
_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最
大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪... 阅读全帖 |
|
C****t
发帖数: 53 | 43 A python version:
def num(maps, s): ######## transform string to 4-based number
digit = 0
for i in range(len(s)):
digit = 4*digit + maps[s[i]]
return digit
def findRepeat(s):
maps = {'A':0, 'C':1,'G':2,'T':3}
bitmap = [0]*pow(4,2)
for i in range(len(s) - 2+1):
bitmap[ num[maps, s[i:i+2] ] += 1
invmaps = {v:k for k,v in maps.items()} ####### reverse maps
for i in range(len(bitmap)):
if bitmap[i] > 1:
print (invmaps[i//4] + in... 阅读全帖 |
|
C****t
发帖数: 53 | 44 A python version:
def num(maps, s): ######## transform string to 4-based number
digit = 0
for i in range(len(s)):
digit = 4*digit + maps[s[i]]
return digit
def findRepeat(s):
maps = {'A':0, 'C':1,'G':2,'T':3}
bitmap = [0]*pow(4,2)
for i in range(len(s) - 2+1):
bitmap[ num[maps, s[i:i+2] ] += 1
invmaps = {v:k for k,v in maps.items()} ####### reverse maps
for i in range(len(bitmap)):
if bitmap[i] > 1:
print (invmaps[i//4] + in... 阅读全帖 |
|
c*****d
发帖数: 6045 | 45 水平低的面试官会考八股，或者从题库里选题
水平高的就会考面很广，不要求你都知道，但是会考察你的思路
有一次我面试G家的oracle database engineer
先问我的经历，我讲到我做过优化
就问我怎么优化的sql语句，我blabla一通，说到index
他问oracle里都有什么index，我答b-tree, bitmap, function
他问b-tree和bitmap有啥区别，我blabla一通
他问null值在b-tree里有没有，我说没有
他问null值在bitmap里有没有，我没注意过，就实话实说，回答估计没有，不确认
他就问你怎么证明你的这个估计，我想了一下，说可以用bbed或者dd看
他就问还有啥简单方法，如果不知道oracle block结构
我考虑了几分钟，突然想到一个最简单的方法
两个有bitmap index的空表
一个load五百万记录，index column都不是null，看Index的大小
一个load五百万记录，index column都是null，看Index的大小
这样就可以知道我猜想的对不对
这样的面试，对面试者也是一个很大的提高
这样... 阅读全帖 |
|
c*****d
发帖数: 6045 | 46 水平低的面试官会考八股，或者从题库里选题
水平高的就会考面很广，不要求你都知道，但是会考察你的思路
有一次我面试G家的oracle database engineer
先问我的经历，我讲到我做过优化
就问我怎么优化的sql语句，我blabla一通，说到index
他问oracle里都有什么index，我答b-tree, bitmap, function
他问b-tree和bitmap有啥区别，我blabla一通
他问null值在b-tree里有没有，我说没有
他问null值在bitmap里有没有，我没注意过，就实话实说，回答估计没有，不确认
他就问你怎么证明你的这个估计，我想了一下，说可以用bbed或者dd看
他就问还有啥简单方法，如果不知道oracle block结构
我考虑了几分钟，突然想到一个最简单的方法
两个有bitmap index的空表
一个load五百万记录，index column都不是null，看Index的大小
一个load五百万记录，index column都是null，看Index的大小
这样就可以知道我猜想的对不对
这样的面试，对面试者也是一个很大的提高
这样... 阅读全帖 |
|
s**********o
发帖数: 14359 | 47 【 以下文字转载自 JobHunting 讨论区 】
发信人: rongxuer (蓉儿), 信区: JobHunting
标 题: 如何秒杀99%的海量数据处理面试题
发信站: BBS 未名空间站 (Thu Apr 5 02:08:57 2012, 美东)
海量数据处理：十道面试题与十个海量数据处理方法总结
作者：July、youwang、yanxionglu。
时间：二零一一年三月二十六日
说明：本文分为俩部分，第一部分为10道海量数据处理的面试题，第二部分为10个海量
数据处理的方法总结。
本文之总结：教你如何迅速秒杀掉：99%的海量数据处理面试题。有任何问题，欢迎随
时交流、指正。
出处：http://blog.csdn.net/v_JULY_v。
------------------------------------------
第一部分、十道海量数据处理面试题
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中
。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的... 阅读全帖 |
|
c*****d
发帖数: 6045 | 48 第一点，当然可以创建bitmap然后and/or操作。但是bitmap和btree index存储方式完
全不同，并不是所有的字段都适合bitmap。你这两个字段都不适合bitmap
第二点，“composite index一般不index单个column，浪费很大”不知道你在说什么。
composite index本来就是在两个字段上作index
cost |
|
b******r
发帖数: 8 | 49 Bitmap bitmap(L"1.img);
Graphics *p=Graphics::FromImage(bitmap);
p->DrawString(L"hello,......);
执行完以后1.img还是没有变化,
bitmap.save("2.img"....)以后新的图象才显示出变化,
我怎么在原来的图象上写上字呢?
谢谢 |
|
b***i
发帖数: 3043 | 50 把问题 再描述一遍
Swing/AWT的一个textPane，背景画图案，分两次画：先画一个bitmap，然后再画一个
。这样，后面那个如果有些点是透明的，就漏出了第一个bitmap的颜色，相当于后面可
以有玻璃的特性。那么后面画的那个bitmap是需要把特定的点变成透明色，这通过awt.
AlphaComposite来实现，画点，线，文字，填充都可以是透明的。后面这个bitmap画到
背景上的时候采用另外一种模式，透明的点则保留下面的颜色。
Javafx我发现无法实现这个把一个Canvas的某个线段变成透明的，或者把一个文字变成
透明的任务。只能把一个矩形区域变透明。变成其它颜色没有问题。比如，Canvas上画
一个蓝色矩形，然后里面画红色文字是正常的。
今天，加入两行程序
PixelWriter pw=gc.getPixelWriter();
pw.setColor(x0+10, y0+10, Color.RED);//把一个点变红色
结果，后面画红色文字，居然拥有了矩形的透明背景。就是说，蓝色矩形中间被扣去一
块，然后那里有红色的文... 阅读全帖 |
|
