第一题:两个数集,都有20亿个数,4G内存,可以使用外存,求两个数集的交集
第二题:原题就是这样的代码,问高并发环境存在的问题,如何改进public class CountServlet extends HttpServlet
{
private volatile static int count;
public void processRequest(HttpServletRequest req)
{
//processRequest
}
public int getCount()
{
return count;
}
public void service(HttpServletRequest req, HttpServletResponse resp)
throws ServletException, IOException
{
count++;
processRequest(req);
PrintWriter out = resp.getWriter();
out.write("hello");
}
}
第二题:原题就是这样的代码,问高并发环境存在的问题,如何改进public class CountServlet extends HttpServlet
{
private volatile static int count;
public void processRequest(HttpServletRequest req)
{
//processRequest
}
public int getCount()
{
return count;
}
public void service(HttpServletRequest req, HttpServletResponse resp)
throws ServletException, IOException
{
count++;
processRequest(req);
PrintWriter out = resp.getWriter();
out.write("hello");
}
}
第二个,把count改为非static的。请指教
另外 这个属性是不是静态在并发这里并不重要
既然提到4G内存了,两个20亿的数据集。
那就将这两个数据集进行拆分,分为较小的数据集。
然后再利用HashSet之类的东西存储遍历的其中一个数据集,然后再遍历第二个,进行判断~ ······
volatile是原子性的吧,请指教,Volatile修饰的成员变量在每次被线程访问时,都强迫从共享内存中重读该成员变量的值。而且,当成员变量发生变化时,强迫线程将变化值回写到共享内存。这样在任何时刻,两个不同的线程总是看到某个成员变量的同一个值。Java语言规范中指出:为了获得最佳速度,允许线程保存共享成员变量的私有拷贝,而且只当线程进入或者离开同步代码块时才与共享成员变量的原始值对比。这样当多个线程同时与某个对象交互时,就必须要注意到要让线程及时的得到共享成员变量的变化。而volatile关键字就是提示VM:对于这个成员变量不能保存它的私有拷贝,而应直接与共享成员变量交互。使用建议:在两个或者更多的线程访问的成员变量上使用volatile。当要访问的变量已在synchronized代码块中,或者为常量时,不必使用。由于使用volatile屏蔽掉了VM中必要的代码优化,所以在效率上比较低,因此一定在必要时才使用此关键字。
正确使用 volatile 变量的条件
您只能在有限的一些情形下使用 volatile 变量替代锁。要使 volatile 变量提供理想的线程安全,必须同时满足下面两个条件:
● 对变量的写操作不依赖于当前值。
● 该变量没有包含在具有其他变量的不变式中。
实际上,这些条件表明,可以被写入 volatile 变量的这些有效值独立于任何程序的状态,包括变量的当前状态。
第一个条件的限制使 volatile 变量不能用作线程安全计数器。虽然增量操作(x++)看上去类似一个单独操作,实际上它是一个由读取-修改-写入操作序列组成的组合操作,必须以原子方式执行,而 volatile 不能提供必须的原子特性。实现正确的操作需要使 x 的值在操作期间保持不变,而 volatile 变量无法实现这点。(然而,如果将值调整为只从单个线程写入,那么可以忽略第一个条件。)
大多数编程情形都会与这两个条件的其中之一冲突,使得 volatile 变量不能像 synchronized 那样普遍适用于实现线程安全。清单 1 显示了一个非线程安全的数值范围类。它包含了一个不变式 —— 下界总是小于或等于上界。
baidu了一下,lz的代码不符合使用volatile 的条件,因为lz代码显然是记访问量的。
所以最后还是要使用synchronized
http://www.ibm.com/developerworks/cn/java/j-jtp06197.html
看这个
对了 补充下 用AtomicInteger也可以
刚才zhao251021539私底下跟我说volatile都是从主内存中读写操作,大致有些了解了
以后有时间再看看去第一题这种方法昨天是这么想的,但是感觉好麻烦的说,比如分成N块,那就是要比较N^2次,比完了还得去交集中的重复部分
内存中开一个byte[256][256][256][32],内存消耗250M(按照1000算,按1024算更小)
每个整数占一个字(bit),
比如:1,000,000,000,十六进制表示为3B9ACA00,
那么在这个byte数组中的位置就是bytes[0x3B]b[0x9A][0xCA][0x00]的第1位(右面第一个bit)如果此bit为0,则表示之前没有1,000,000,000,如果此bit为1,则说明出现过比如:1,000,000,十六进制表示为000F4240,
那么在这个byte数组中的位置就是bytes[0x00]b[0x0F][0x42][0x08]的第1位如果此bit为0,则表示之前没有1,000,000,如果此bit为1,则说明出现过相关公式(不考虑负数,如有负数,考虑使用>>>
bytes[x >> 24][(x >> 16) & 0xFF][(x >> 8) & 0xFF][(x >> 3) % 32],每一个byte的计算:
bytes[x >> 24][(x >> 16) & 0xFF][(x >> 8) & 0xFF][(x >> 3) % 32] |= 1 << (x % 8);
public static void main(String[] args) throws Exception {
byte[][][][] bytes = new byte[256][256][256][32];
for (int x = 0; x < 2000000; x++) {
bytes[x >> 24][(x >> 16) & 0xFF][(x >> 8) & 0xFF][(x >> 3) % 32] |= 1 << (x % 8);
System.out
.printf("%d: bytes[%d][%d][%d][%d] = %x %n",
x,
x >> 24,
(x >> 16) & 0xFF,
(x >> 8) & 0xFF,
(x >> 3) % 32,
bytes[x >> 24][(x >> 16) & 0xFF][(x >> 8) & 0xFF][(x >> 3) % 32]);
}
}
-Xmx2048m 就可以跑了
要判断1993480是否存在的话,那么就去bytes[0][30][107][1],判断右面第一位(1993480 % 8 = 0)。
if ((bytes[x >> 24][(x >> 16) & 0xFF][(x >> 8) & 0xFF][(x >> 3) % 32] | (1 << (x % 8)))!=0)如果这个数组保存的结果是0xF0或者0x28,那么说明右面第一位是0,那么1993480不存在
如果这个数组保存的结果是0xFF或者0x21,那么说明右面第一位是1,那么1993480存在
byte[256][256][256][32]除了256*256*256*32bytes外,还有
256个byte[][][]数组
256×256个byte[][]
....
所以我一开始设置-Xmx800m还不够不过,如果直接byte[256*256*256*32]的话,内存消耗小了,但是貌似访问速度会慢很多。具体如何权衡,没有tuning过
这个地方不太了解,还请坦克前辈再指点下~
请你搜索下容器启动后Servlet会有几个实例...
不是默认是单例 跟单例无关..遵循规范的容器只创建一个实例(但不是那个什么单例 因为你要是乐意的话你可以自己new几个Servlet玩)
不遵循的就可能创建多个实例(我也不知道 乱喷的)
第二题应该用原子INT.