首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
  • 【算法比赛】如何存储Hash结构 [已结贴,结贴人:iuhxq]
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • iuhxq
    • 等级:
    发表于:2008-04-12 16:52:59 楼主
    有个hashtable,如果hash里保存了几百万的数据,怎么把这些数据保存到硬盘上,下次读取的时候能够最快的恢复这个hash结构

    方便测试和对比,统一代码框架如下:
    [code=C#]using System;
    using System.Collections.Generic;
    using System.Collections;

    public class MyClass
    {
    public static void Main()
    {
    long vTickCount = Environment.TickCount;
    Hashtable hash = init();
    WL("用时:{0}毫秒", Environment.TickCount-vTickCount);

    //写入文件
    vTickCount = Environment.TickCount;
    WriteFile("e:/hash.dat");
    WL("用时:{0}毫秒", Environment.TickCount-vTickCount);

    //从文件中读取,恢复Hash结构
    vTickCount = Environment.TickCount;
    hash = ReadFile("e:/hash.dat");
    WL("用时:{0}毫秒", Environment.TickCount-vTickCount);

    RL();
    }

    public static void WriteFile(string file)
    {
    //自由发挥
    }

    public static Hashtable ReadFile(string file)
    {
    //自由发挥
    return null;
    }

    public static Hashtable init()
    {
    Hashtable hash = new Hashtable();
    for(int i=0;i <4000000;i++)
    {
    hash.Add(Guid.NewGuid().ToString(), i);
    }
    WL("完成");
    return hash;
    }

    #region Helper methods

    private static void WL(object text, params object[] args)
    {
    Console.WriteLine(text.ToString(), args);
    }

    private static void RL()
    {
    Console.ReadLine();
    }

    private static void Break()
    {
    System.Diagnostics.Debugger.Break();
    }

    #endregion
    }[code]

    奖励:
    第一名100分
    第二名50分
    其他酌情散掉。
    200  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-12 17:06:021楼 得分:7
    帮你顶一下!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • iuhxq
    • 等级:
    发表于:2008-04-12 17:09:212楼 得分:0
    C# code
    using System; using System.Collections.Generic; using System.Collections; public class MyClass { public static void Main() { long vTickCount = Environment.TickCount; Hashtable hash = init(); WL("用时:{0}毫秒", Environment.TickCount-vTickCount); //写入文件 vTickCount = Environment.TickCount; WriteFile("e:/hash.dat"); WL("用时:{0}毫秒", Environment.TickCount-vTickCount); //从文件中读取,恢复Hash结构 vTickCount = Environment.TickCount; hash = ReadFile("e:/hash.dat"); WL("用时:{0}毫秒", Environment.TickCount-vTickCount); RL(); } public static void WriteFile(string file) { //自由发挥 } public static Hashtable ReadFile(string file) { //自由发挥 return null; } public static Hashtable init() { Hashtable hash = new Hashtable(); for(int i=0;i <4000000;i++) { hash.Add(Guid.NewGuid().ToString(), i); } WL("完成"); return hash; } #region Helper methods private static void WL(object text, params object[] args) { Console.WriteLine(text.ToString(), args); } private static void RL() { Console.ReadLine(); } private static void Break() { System.Diagnostics.Debugger.Break(); } #endregion }
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-12 17:15:593楼 得分:7
    有情帮顶
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • badtank
    • 等级:
    发表于:2008-04-12 17:20:534楼 得分:7
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-12 17:23:335楼 得分:7
    很像是三级考试试题
    但比那个要难
    我有想法,但没时间
    hehe
    用system.io流
    读写到硬盘就ok了
    至于效率吗?还没考虑过!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-12 18:33:026楼 得分:7
    占个位
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-12 19:50:207楼 得分:0
    该回复于2008-04-12 20:16:41被版主删除
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • iuhxq
    • 等级:
    发表于:2008-04-13 19:02:018楼 得分:0
    顶顶先
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • iuhxq
    • 等级:
    发表于:2008-04-14 09:34:499楼 得分:0
    再顶顶,周一了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-14 10:59:5310楼 得分:7
    UP下~
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-14 11:06:3811楼 得分:7
    看过顶过,回去想想
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • ph580
    • 等级:
    发表于:2008-04-14 11:21:1712楼 得分:7
    不会吧
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-14 11:33:4713楼 得分:7
    不会,帮顶
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • viena
    • 等级:
    发表于:2008-04-14 11:39:1614楼 得分:7
    内存文件映射
    转贴个
    http://zhidao.baidu.com/question/40508551.html?fr=qrl
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zswang
    • 等级:
    发表于:2008-04-14 17:38:2215楼 得分:7
    怎么验证正确性?关注一下。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-14 17:44:1316楼 得分:7
    关注..
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-14 17:47:1817楼 得分:0
    该回复于2008-04-14 18:00:47被版主删除
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-14 17:53:3818楼 得分:7
    给点粥喝喝吧
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-14 18:28:4519楼 得分:7
    只能up了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zswang
    • 等级:
    发表于:2008-04-14 18:59:5620楼 得分:7
    hash?demo10
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zswang
    • 等级:
    发表于:2008-04-14 19:02:3421楼 得分:7
    不用考虑效率,我在想如果结果是放在Hashtable对象中,那么能通过内存访问吗?不然Add()百万次避免不了。。。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • akirya
    • 等级:
    发表于:2008-04-14 20:19:1922楼 得分:7
    还以为是在内存中呢

    有一个 bdb 文件数据库,效率不错.
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-14 20:45:5323楼 得分:7
    帮顶!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-14 20:48:1224楼 得分:7
    C# code
    using System.Runtime.InteropServices; [DllImport("kernel32.dll")] public static extern IntPtr CreateFileMapping(IntPtr hFile, IntPtr lpFileMappingAttributes, uint flProtect, uint dwMaximumSizeHigh, uint dwMaximumSizeLow, string lpName); [DllImport("kernel32.dll")] public static extern IntPtr MapViewOfFile(IntPtr hFileMappingObject, uint dwDesiredAccess, uint dwFileOffsetHigh, uint dwFileOffsetLow, IntPtr dwNumberOfBytesToMap); [DllImport("kernel32.dll")] public static extern bool UnmapViewOfFile(IntPtr lpBaseAddress); [DllImport("kernel32.dll")] public static extern bool CloseHandle(IntPtr hObject); [DllImport("kernel32.dll")] public static extern IntPtr CreateFile(string lpFileName, int dwDesiredAccess, FileShare dwShareMode, IntPtr securityAttrs, FileMode dwCreationDisposition, int dwFlagsAndAttributes, IntPtr hTemplateFile); [DllImport("kernel32.dll")] public static extern uint GetFileSize(IntPtr hFile, IntPtr lpFileSizeHigh); public const int GENERIC_READ = -2147483648; //0x80000000 public const int GENERIC_WRITE = 0x40000000; public const int GENERIC_EXECUTE = 0x20000000; public const int GENERIC_ALL = 0x10000000; public const int FILE_ATTRIBUTE_NORMAL = 0x80; public const int FILE_FLAG_SEQUENTIAL_SCAN = 0x8000000; public const int INVALID_HANDLE_VALUE = -1; public const int PAGE_NOACCESS = 1; public const int PAGE_READONLY = 2; public const int PAGE_READWRITE = 4; public const int FILE_MAP_COPY = 1; public const int FILE_MAP_WRITE = 2; public const int FILE_MAP_READ = 4; private void button1_Click(object sender, EventArgs e) { IntPtr vFileHandle = CreateFile(@"c:\temp\temp.txt", GENERIC_READ | GENERIC_WRITE, FileShare.Read | FileShare.Write, IntPtr.Zero, FileMode.Open, FILE_ATTRIBUTE_NORMAL | FILE_FLAG_SEQUENTIAL_SCAN, IntPtr.Zero); if (INVALID_HANDLE_VALUE != (int)vFileHandle) { IntPtr vMappingHandle = CreateFileMapping( vFileHandle, IntPtr.Zero, PAGE_READWRITE, 0, 0, "~MappingTemp"); if (vMappingHandle != IntPtr.Zero) { IntPtr vHead = MapViewOfFile(vMappingHandle, FILE_MAP_COPY | FILE_MAP_READ | FILE_MAP_WRITE, 0, 0, IntPtr.Zero); if (vHead != IntPtr.Zero) { uint vSize = GetFileSize(vFileHandle, IntPtr.Zero); for (int i = 0; i <= vSize / 2; i++) { byte vTemp = Marshal.ReadByte((IntPtr)((int)vHead + i)); Marshal.WriteByte((IntPtr)((int)vHead + i), Marshal.ReadByte((IntPtr)((int)vHead + vSize - i - 1))); Marshal.WriteByte((IntPtr)((int)vHead + vSize - i - 1), vTemp); } UnmapViewOfFile(vHead); } CloseHandle(vMappingHandle); } CloseHandle(vFileHandle); } }
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • iuhxq
    • 等级:
    发表于:2008-04-14 22:01:3825楼 得分:0
    实际情况是放数据库里的,然后蜘蛛排重的时候,把URL编码后放到hashtable里。
    每次取到新的url去比较下是否存在(排除重复)
    为了实现断点续抓,关闭蜘蛛的时候,数据存在数据库里,启动蜘蛛的时候,再加载到hashtable里

    引用 20 楼 zswang 的回复:
    请教一下,楼主所说的hash结构怎么取出来?又怎么写进去?给个demo看看,只要读写10条的例子即可!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • iuhxq
    • 等级:
    发表于:2008-04-14 22:03:0726楼 得分:0
    我感觉性能损失是损失在建立hash结构上了。读取文件或者读取数据库速度没啥提升空间。

    主要是能把hash结构直接保存起来,下次不用再去建立这个结构就会快很多。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • webhaitao
    • 等级:
    发表于:2008-04-14 23:48:3427楼 得分:7
    有意思,想想
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-15 09:14:1928楼 得分:6
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-04-15 09:14:2329楼 得分:6
    帮顶
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天